This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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]));
}
}
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] == INF ? -1 : DP[i][cnt%2]) << ' ';
}
}
Compilation message (stderr)
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |