EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2016
ICPC 2016

B. Branch Assignment

The Innovative Consumer Products Company (ICPC) is planning to start a top-secret project. This project consists of s subprojects. There will be b ≥ s branches of ICPC involved in this project and ICPC wants to assign each branch to one of the subprojects....

Updated May 21, 2026
Track ICPC
Year 2016
Statement Text + PDF
TeXC++Statement textStatement PDF
Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF
Time limit 3 seconds

The Innovative Consumer Products Company (ICPC) is planning to start a top-secret project. This project consists of s subprojects. There will be b ≥ s branches of ICPC involved in this project and ICPC wants to assign each branch to one of the subprojects. In other words, the branches will form s disjoint groups, with each group in charge of a subproject. At the end of each month, each branch will send a message to every other branch in its group (a different message to each branch). ICPC has a particular protocol for its communications. Each branch i has a secret key ki known only to the branch and the ICPC headquarters. Assume branch i wants to send a message to branch j. Branch i encrypts its message with its key ki . A trusted courier picks up this message from this branch and delivers it to the ICPC headquarters. Headquarters decrypts the message with key ki and re-encrypts it with key kj . The courier then delivers this newly encrypted message to branch j, which decrypts it with its own key kj . For security reasons, a courier can carry only one message at a time. Given a road network and the locations of branches and the headquarters in this network, your task is to determine the minimum total distance that the couriers will need to travel to deliver all the end-of-month messages, over all possible assignments of branches to subprojects.

Input

The first line of input contains four integers n, b, s, and r, where n (2 ≤ n ≤ 5 000) is the number of intersections, b (1 ≤ b ≤ n − 1) is the number of branches, s (1 ≤ s ≤ b) is the number of subprojects, and r (1 ≤ r ≤ 50 000) is the number of roads. The intersections are numbered from 1 through n. The branches are at intersections 1 through b, and the headquarters is at intersection b + 1. Each of the next r lines contains three integers u, v, and `, indicating a one-way road from intersection u to a different intersection v (1 ≤ u, v ≤ n) of length ` (0 ≤ ` ≤ 10 000). No ordered pair (u, v) appears more than once, and from any intersection it is possible to reach every other intersection.

Output

Display the minimum total distance that the couriers will need to travel.

Sample Tests

Sample 1
Sample Input 
5   4   2 10
5   2   1
2   5   1
3   5   5
4   5   0
1   5   1
2   3   1
3   2   5
2   4   5
2   1   1
3   4   2
Sample Output 
13
Sample 2
Sample Input 
5   4   2 10
5   2   1
2   5   1
3   5   5
4   5   10
1   5   1
2   3   1
3   2   5
2   4   5
2   1   1
3   4   2
Sample Output 
24
Editorial

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

  • Write the structural observations that make the problem tractable.

  • State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.

  • If the constraints matter, explain exactly which part of the solution they enable.

Algorithm

  1. Describe the data structures and the state maintained by the algorithm.

  2. Explain the processing order and why it is sufficient.

  3. Mention corner cases explicitly if they affect the implementation.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

State the first key claim.

Proof.

Provide a concise proof.

Lemma 2.

State the next claim if needed.

Proof.

Provide a concise proof.

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

Combine the lemmas and finish the argument.

Complexity Analysis

State the running time and memory usage in terms of the input size.

Implementation Notes

  • Mention any non-obvious implementation detail that is easy to get wrong.

  • Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.

Implementation

Code

C++ solution used for this page.

C++

Clean code view with a raw-file link when you want the original source.

Raw file 
#include <bits/stdc++.h>
using namespace std;

namespace {

void solve() {
    // Fill in the full solution logic for the problem here.
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2016/B-branch-assignment/solution.texC++ implementationcompetitive_programming/icpc/2016/B-branch-assignment/solution.cppStatement textcompetitive_programming/icpc/2016/B-branch-assignment/statement.txtStatement PDFcompetitive_programming/icpc/2016/B-branch-assignment/statement.pdfMetadatacompetitive_programming/icpc/2016/B-branch-assignment/meta.jsonYear packetcompetitive_programming/icpc/2016/contest_problems.pdf