Submission #696340

#	Time	Username	Problem	Language	Result	Execution time	Memory
696340		Cross_Ratio	Travelling Merchant (CCO21_day2problem1)	C++14	4 / 25	2065 ms	15148 KiB

Main

#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;
      |            ^

• Subtask 1: 4 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16