제출 #1102513

#제출 시각아이디문제언어결과실행 시간메모리
1102513daoquanglinh2007Travelling Merchant (CCO21_day2problem1)C++17
0 / 25
177 ms44132 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...