Submission #1102513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102513		daoquanglinh2007	Travelling Merchant (CCO21_day2problem1)	C++17	0 / 25	177 ms	44132 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 2e5, inf = 1e9+7;

int N, M;
vector <pair <int, pii> > adj[NM+5], par[NM+5];
int timer = 0, num[NM+5], low[NM+5];
int comp = 0, scc[NM+5];
vector <int> arr[NM+5];
stack <int> st;
vector <int> adj_comp[NM+5];
int deg[NM+5];
vector <int> topo;
int ans[NM+5];

void dfs(int u){
    num[u] = low[u] = ++timer;
    st.push(u);
    for (pair <int, pii> _ : adj[u]){
        int v = _.fi;
        if (scc[v]) continue;
        if (num[v]){
            low[u] = min(low[u], num[v]);
        }
        else{
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
    }
    if (low[u] == num[u]){
        comp++;
        int v = -1;
        while (v != u){
            v = st.top();
            scc[v] = comp;
            st.pop();
        }
    }
}

void topo_sort(){
    while (!st.empty()) st.pop();
    for (int i = 1; i <= comp; i++)
        if (!deg[i]) st.push(i);
    while (!st.empty()){
        int u = st.top(); st.pop();
        topo.push_back(u);
        for (int v : adj_comp[u]){
            deg[v]--;
            if (!deg[v]) st.push(v);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    while (M--){
        int u, v, r, p; cin >> u >> v >> r >> p;
        adj[u].push_back(mp(v, mp(r, p)));
        par[v].push_back(mp(u, mp(r, p)));
    }
    for (int i = 1; i <= N; i++){
        if (num[i]) continue;
        dfs(i);
    }
    for (int i = 1; i <= N; i++)
        arr[scc[i]].push_back(i);
    
    for (int u = 1; u <= N; u++)
        for (pair <int, pii> _ : adj[u]){
            int v = _.fi;
            if (scc[v] == scc[u]) continue;
            adj_comp[scc[u]].push_back(scc[v]);
            deg[scc[v]]++;
        }
    topo_sort();
    reverse(topo.begin(), topo.end());

    for (int i = 1; i <= N; i++) ans[i] = +inf;

    for (int c : topo){
        while (!st.empty()) st.pop();
        int mx = 0;
        for (int u : arr[c]){
            for (pair <int, pii> _ : adj[u]){
                int v = _.fi, r = _.se.fi, p = _.se.se;
                if (scc[v] == scc[u]){
                    mx = max(mx, r);
                    continue;
                }
                if (ans[v] == +inf) continue;
                if (ans[u] == +inf) st.push(u);
                ans[u] = min(ans[u], max(r, ans[v]-p));
            }
        }
        for (int u : arr[c]){
            for (pair <int, pii> _ : adj[u]){
                int v = _.fi, r = _.se.fi;
                if (scc[v] == scc[u] && r == mx){
                    if (ans[u] == +inf) st.push(u);
                    ans[u] = min(ans[u], r);
                }
            }
        }
        while (!st.empty()){
            int u = st.top(); st.pop();
            for (pair <int, pii> _ : par[u]){
                int v = _.fi, r = _.se.fi, p = _.se.se;
                if (ans[v] <= max(r, ans[u]-p)) continue;
                ans[v] = max(r, ans[u]-p);
                st.push(v);
            }
        }
    }
    for (int i = 1; i <= N; i++)
        cout << (ans[i] == +inf ? -1 : ans[i]) << ' ';
    return 0;
}

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