Submission #1102534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102534		adaawf	Travelling Merchant (CCO21_day2problem1)	C++17	25 / 25	115 ms	18768 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct EDGE {
    int x, y, z, t;
} e[200005];
bool cmp(EDGE aa, EDGE bb) {
    return aa.z < bb.z;
}
vector<int> gg[200005];
int d[200005], da[200005], f[200005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z, t;
        cin >> x >> y >> z >> t;
        d[x]++;
        e[i] = {x, y, z, t};
    }
    sort(e + 1, e + m + 1, cmp);
    queue<int> q;
    for (int i = 1; i <= m; i++) {
        gg[e[i].y].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        if (d[i] == 0) q.push(i);
        f[i] = 2e9;
    }
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        f[p] = -1;
        for (int w : gg[p]) {
            d[e[w].x]--;
            da[w] = 1;
            if (d[e[w].x] == 0) {
                q.push(e[w].x);
            }
        }
    }
    for (int i = m; i >= 1; i--) {
        if (da[i]) continue;
        f[e[i].x] = min(f[e[i].x], e[i].z);
        d[e[i].x]--;
        da[i] = 1;
        if (d[e[i].x] == 0) {
            queue<int> q;
            q.push(e[i].x);
            while (!q.empty()) {
                int p = q.front();
                q.pop();
                for (int w : gg[p]) {
                    if (da[w] == 1) continue;
                    f[e[w].x] = min(f[e[w].x], max(f[p] - e[w].t, e[w].z));
                    da[w] = 1;
                    d[e[w].x]--;
                    if (d[e[w].x] == 0) {
                        q.push(e[w].x);
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) cout << f[i] << " ";
}

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