Submission #696340

#TimeUsernameProblemLanguageResultExecution timeMemory
696340Cross_RatioTravelling Merchant (CCO21_day2problem1)C++14
4 / 25
2065 ms15148 KiB
#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 (stderr)

Main.cpp: In function 'int main()':
Main.cpp:13:12: warning: unused variable 'j' [-Wunused-variable]
   13 |     int i, j;
      |            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...