#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
vector<array<int, 3>> adj[200005];
int DP[200005][2];
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
int i, j;
for(i=0;i<M;i++) {
int a, b, r, p;
cin >> a >> b >> r >> p;
adj[b-1].push_back({a-1, r, p});
}
int cnt = 1;
while(true) {
for(i=0;i<N;i++) DP[i][cnt%2] = INF;
for(i=0;i<N;i++) {
for(auto n2 : adj[i]) {
DP[n2[0]][cnt%2] = min(DP[n2[0]][cnt%2], max(n2[1], DP[i][(cnt+1)%2] - n2[2]));
}
}
for(i=0;i<N;i++) {
if(DP[i][cnt%2] >= 1e12) DP[i][cnt%2] = INF;
}
bool isSame = true;
for(i=0;i<N;i++) {
if(DP[i][cnt%2] != DP[i][(cnt+1)%2]) isSame = false;
}
if(isSame) break;
cnt++;
}
for(i=0;i<N;i++) {
cout << (DP[i][cnt%2] >= 1e12 ? -1 : DP[i][cnt%2]) << ' ';
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:13:12: warning: unused variable 'j' [-Wunused-variable]
13 | int i, j;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5076 KB |
Output is correct |
2 |
Correct |
4 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
4 ms |
5076 KB |
Output is correct |
5 |
Correct |
3 ms |
5076 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
3 ms |
5076 KB |
Output is correct |
8 |
Correct |
44 ms |
5104 KB |
Output is correct |
9 |
Correct |
5 ms |
5076 KB |
Output is correct |
10 |
Correct |
3 ms |
5076 KB |
Output is correct |
11 |
Correct |
4 ms |
5204 KB |
Output is correct |
12 |
Correct |
3 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5076 KB |
Output is correct |
14 |
Correct |
43 ms |
5076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1457 ms |
15076 KB |
Output is correct |
2 |
Correct |
1371 ms |
15148 KB |
Output is correct |
3 |
Correct |
63 ms |
12200 KB |
Output is correct |
4 |
Correct |
27 ms |
9044 KB |
Output is correct |
5 |
Correct |
249 ms |
14080 KB |
Output is correct |
6 |
Correct |
238 ms |
14116 KB |
Output is correct |
7 |
Correct |
86 ms |
11600 KB |
Output is correct |
8 |
Execution timed out |
2065 ms |
14384 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5076 KB |
Output is correct |
2 |
Correct |
4 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
4 ms |
5076 KB |
Output is correct |
5 |
Correct |
3 ms |
5076 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
3 ms |
5076 KB |
Output is correct |
8 |
Correct |
44 ms |
5104 KB |
Output is correct |
9 |
Correct |
5 ms |
5076 KB |
Output is correct |
10 |
Correct |
3 ms |
5076 KB |
Output is correct |
11 |
Correct |
4 ms |
5204 KB |
Output is correct |
12 |
Correct |
3 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5076 KB |
Output is correct |
14 |
Correct |
43 ms |
5076 KB |
Output is correct |
15 |
Correct |
1457 ms |
15076 KB |
Output is correct |
16 |
Correct |
1371 ms |
15148 KB |
Output is correct |
17 |
Correct |
63 ms |
12200 KB |
Output is correct |
18 |
Correct |
27 ms |
9044 KB |
Output is correct |
19 |
Correct |
249 ms |
14080 KB |
Output is correct |
20 |
Correct |
238 ms |
14116 KB |
Output is correct |
21 |
Correct |
86 ms |
11600 KB |
Output is correct |
22 |
Execution timed out |
2065 ms |
14384 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |