Submission #457865

#TimeUsernameProblemLanguageResultExecution timeMemory
457865ritul_kr_singhRigged Roads (NOI19_riggedroads)C++17
17 / 100
553 ms262148 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define sp << ' ' << #define nl << '\n' const int Z = 3e5+1; int n, e, S[Z], T[Z], h[2][Z], p[Z], d[Z], pEdge[Z], ans[Z]; bool inMST[Z]; vector<array<int, 2>> g[Z]; int find(int u){ return S[u] < 0 ? u : S[u] = find(S[u]); } void unite(int u, int v){ if(S[u] > S[v]) swap(u, v); if(u != v){ if(d[T[u]] > d[T[v]]) T[u] = T[v]; S[u] += S[v], S[v] = u; } } void dfs(int u, int par, int dep, int edge){ d[u] = dep; p[u] = par; pEdge[u] = edge; for(auto &[v, w] : g[u]) if(v != par) dfs(v, u, dep+1, w); } signed main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> e; for(int i=1; i<=e; ++i){ cin >> h[0][i] >> h[1][i]; } for(int i=1; i<n; ++i){ int j; cin >> j; inMST[j] = 1; g[h[0][j]].push_back({h[1][j], j}); g[h[1][j]].push_back({h[0][j], j}); } dfs(1, 1, 0, 0); fill(S+1, S+n+1, -1); iota(T+1, T+n+1, +1); int j = 1; for(int i=1; i<=e; ++i){ int u = find(h[0][i]), v = find(h[1][i]); if(inMST[i] && !ans[i]){ ans[i] = j++; unite(u, v); } if(!ans[i]){ vector<int> curr; while(u != v){ if(d[T[u]] < d[T[v]]) swap(u, v); curr.push_back(pEdge[T[u]]); unite(u, find(p[T[u]])); u = find(u); } sort(begin(curr), end(curr)); for(int &w : curr) ans[w] = j++; ans[i] = j++; } cout << ans[i] << ' '; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...