USACO 2020 February Contest, Gold Problem 1. Timeline

USACO 2020 February Contest, Gold Problem 1. Timeline

Bessie attended NN milking sessions (1N1051≤N≤105) over the past MM days (2M1092≤M≤109). However, she is having trouble remembering when she attended each session.

For each session i=1Ni=1…N, she knows that it occurred no earlier than day SiSi (1SiM1≤Si≤M). Additionally, Bessie has CC memories (1C1051≤C≤105), each described by a triple (a,b,x)(a,b,x), where she recalls that session bb happened at least xx days after aa.

Help Bessie by computing the earliest possible date of occurrence for each milking session. It is guaranteed that Bessie did not remember incorrectly; in other words, there exists an assignment of sessions to days in the range 1M1…M such that all constraints from her memories are satisfied.



  • Test cases 2-4 satisfy N,C103N,C≤103.
  • Test cases 5-10 satisfy no additional constraints.



The first line of input contains NNMM, and CC.The next line contains NN space-separated integers S1,S2,,SNS1,S2,…,SN. Each is in the range 1M1…M.

The next CC lines contain three integers, aabb, and xx indicating that session bb happened at least xx days after aa. For each line, aba≠baa and bb are in the range 1N1…N, and xx is in the range 1M1…M.


OUTPUT FORMAT (file timeline.out):

Output NN lines giving the earliest possible date of occurrence for each session.



4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 4



Session two occurred at least five days after session one, so it cannot have occurred before day 1+5=6.1+5=6. Session four occurred at least two days after session two, so it cannot have occurred before day 6+2=86+2=8.


Problem credits: Mark Gordon

USACO 2020 February Contest, Gold Problem 1. Timeline 题解(翰林国际教育提供,仅供参考)



(Analysis by Benjamin Qi)

For each constraint (a,b,x)(a,b,x) draw a directed edge from aa to bb with weight xx. Note that there cannot be a cycle in this graph or else no solution would exist. Thus, we'll process the sessions in order of the topological sort.

Without loss of generality suppose that the topological sort is 1,2,,N,1,2,…,N, meaning that all edges satisfy a<ba<b. Then for each directed edge in increasing order of aa, it suffices to set Sb=max(Sb,Sa+x)Sb=max(Sb,Sa+x). After all of these edges are processed, the resulting S1,S2,,SNS1,S2,…,SN are the lowest possible values that satisfy all the edge conditions (assuming all of them are less than or equal to MM). This can be implemented in O(N+M)O(N+M) time.


#include "bits/stdc++.h"

using namespace std;

void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 

#define f first
#define s second

const int MX = 1e5+5;

int N,M,C,S[MX],in[MX];
bool vis[MX];
vector<pair<int,int>> adj[MX];
queue<int> q;
int main() {
	cin >> N >> M >> C; 
	for (int i = 1; i <= N; ++i) cin >> S[i];
	for (int i = 0; i < C; ++i) {
		int a,b,x; cin >> a >> b >> x;
		adj[a].push_back({b,x}); in[b] ++;
	for (int i = 1; i <= N; ++i) if (!in[i]) q.push(i);
	while (q.size()) {
		int x = q.front(); q.pop(); // process x in order of topological sort
		vis[x] = 1; assert(S[x] <= M);
		for (auto& t: adj[x]) {
			S[t.f] = max(S[t.f],S[x]+t.s);
			if (!(--in[t.f])) q.push(t.f);
	for (int i = 1; i <= N; ++i) {
		cout << S[i] << "\n";