Home » 国际竞赛 » Details

USACO 2020 February Contest, Gold Problem 1. Timeline

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午2:41

USACO 2020 February Contest, Gold Problem 1. Timeline

Bessie attended $N$ milking sessions ( $1 \leq N \leq 10^{5}$ ) over the past $M$ days ( $2 \leq M \leq 10^{9}$ ). However, she is having trouble remembering when she attended each session.

For each session $i = 1 \dots N$ , she knows that it occurred no earlier than day $S_{i}$ ( $1 \leq S_{i} \leq M$ ). Additionally, Bessie has $C$ memories ( $1 \leq C \leq 10^{5}$ ), each described by a triple $(a, b, x)$ , where she recalls that session $b$ happened at least $x$ days after $a$ .

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 $1 \dots M$ such that all constraints from her memories are satisfied.

SCORING:

Test cases 2-4 satisfy $N, C \leq 10^{3}$ .
Test cases 5-10 satisfy no additional constraints.

INPUT FORMAT (file timeline.in):

The first line of input contains $N$ , $M$ , and $C$ .The next line contains $N$ space-separated integers $S_{1}, S_{2}, \dots, S_{N}$ . Each is in the range $1 \dots M$ .

The next $C$ lines contain three integers, $a$ , $b$ , and $x$ indicating that session $b$ happened at least $x$ days after $a$ . For each line, $a \neq b$ , $a$ and $b$ are in the range $1 \dots N$ , and $x$ is in the range $1 \dots M$ .

OUTPUT FORMAT (file timeline.out):

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

SAMPLE INPUT:

SAMPLE OUTPUT:

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

Problem credits: Mark Gordon

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

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

For each constraint $(a, b, x)$ draw a directed edge from $a$ to $b$ with weight $x$ . 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, \dots, N,$ meaning that all edges satisfy $a < b$ . Then for each directed edge in increasing order of $a$ , it suffices to set $S_{b} = max (S_{b}, S_{a} + x)$ . After all of these edges are processed, the resulting $S_{1}, S_{2}, \dots, S_{N}$ are the lowest possible values that satisfy all the edge conditions (assuming all of them are less than or equal to $M$ ). This can be implemented in $O (N + M)$ time.

#include "bits/stdc++.h"

using namespace std;

void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

#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() {
	setIO("timeline");
	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) {
		assert(vis[i]);
		cout << S[i] << "\n";
	}
}

[/hide]

以上就是关于【USACO 2020 February Contest, Gold Problem 1. Timeline】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

美国AI奥赛首次新增低龄组！2027 USAAIO报名中，2月正式开考！

不考编程实操？2026 CAICP人工智能能力认证首轮11月22日开考，备考指南速递！