Submission #1156842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156842		antonn	Escape Route (JOI21_escape_route)	C++20	Compilation error	0 ms	0 KiB

escape_route

#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const ll inf = 1e18;


struct aboba {
    ll time;
    ll extend;
    ll node;
};

bool operator < (aboba a, aboba b) {
    if (a.time == b.time) {
        return a.extend > b.extend;
    }
    return a.time > b.time;
}


vector<ll> calculate_necessary_time(int N, int M, ll S, int Q, vector<int> A, vector<int> B, vector<ll> L, vector<ll> C, vector<int> U, vector<int> V, vector<ll> T) {
    vector<vector<array<ll, 3>>> g(N);
    for (int i = 0; i < M; i += 1) {
        g[A[i]].push_back({B[i], L[i], C[i]});
        g[B[i]].push_back({A[i], L[i], C[i]});
    }
    vector<vector<vector<pair<ll, ll>>>> paths(N, vector<vector<pair<ll, ll>>>(N)); 
    vector<vector<ll>> zero_delay(N, vector<ll>(N, inf));
    for (int u = 0; u < N; u += 1) {
        priority_queue<aboba> pq;
        pq.push({0, -inf, u});
        paths[u][u].push_back({0, inf});
        vector<int> vis(N);
        while (!pq.empty()) {
            aboba x = pq.top();
            pq.pop();
            ll t = -x.time;
            ll e = -x.extend;
            int node = x.node;
            if (vis[node] > N) {
                break;
            }
            vis[node] += 1;
            for (auto [v, l, c] : g[node]) {
                ll could = c - (t + l);
                if (could < 0) {
                    continue;
                }
                bool bad = 0;
                for (auto [time, extend] : paths[u][v]) {
                    if (t + l >= time && min(e, could) <= extend) {
                        bad = 1;
                        break;
                    }
                }
                if (!bad) {
                    zero_delay[u][v] = min(zero_delay[u][v], t + l); 
                    paths[u][v].push_back({t + l, min(e, could)});
                    pq.push({-(t + l), -min(e, could), v});
                }
            }
        }
    }
    for (int u = 0; u < N; u += 1) {
        zero_delay[u][u] = 0;
    }
    
    vector<vector<ll>> dist(N, vector<ll>(N, inf));
    for (int u = 0; u < N; u += 1) {
        for (int v = 0; v < N; v += 1) {
            if (zero_delay[u][v] <= S) {
                dist[u][v] = zero_delay[u][v];
            }
        }
    }
    for (int st = 0; st < 100; st += 1) {
        for (int w = 0; w < N; w += 1) {
            for (int u = 0; u < N; u += 1) {
                for (int v = 0; v < N; v += 1) {
                    dist[u][v] = min(dist[u][v], dist[u][w] + (dist[u][w] == 0 ? 0 : S - dist[u][w] % S) + zero_delay[w][v]);
                }
            }
        }
    }
    vector<ll> sol(Q);
    for (int i = 0; i < Q; i += 1) {
        ll ans = 1e18;
        ans = S - T[i] + dist[U[i]][V[i]];
        for (int w = 0; w < N; w += 1) {
            for (auto [time, extend] : paths[U[i]][w]) {
                if (extend >= T[i]) {
                    if (w == V[i]) {
                        ans = min(ans, time);
                    } else {
                        ans = min(ans, S - T[i] + dist[w][V[i]]);
                    }
                }
            }
        }
        sol[i] = ans;
    }
    return sol;
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int N, M, Q;
    ll S;
    cin >> N >> M >> S >> Q;
    vector<int> A(M), B(M), U(Q), V(Q);
    vector<ll> T(Q), L(M), C(M);
    for (int i = 0; i < M; i += 1) {
        cin >> A[i] >> B[i] >> L[i] >> C[i];
    }
    for (int i = 0; i < Q; i += 1) {
        cin >> U[i] >> V[i] >> T[i];
    }
    vector<ll> sol = calculate_necessary_time(N, M, S, Q, A, B, L, C, U, V, T);
    for (int i = 0; i < sol.size(); i += 1) {
        cout << sol[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc5vRwvp.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cctInqsV.o:escape_route.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status