Submission #877172

#TimeUsernameProblemLanguageResultExecution timeMemory
877172phongRigged Roads (NOI19_riggedroads)C++17
100 / 100
293 ms70092 KiB
#include<bits/stdc++.h> #define ll long long const int nmax = 3e5 + 5; const ll oo = 1e18; const int lg = 20; const int bs = 16785; const int ts = 16767; const ll mod = 1e9 + 7; #define pii pair<int, int> #define fi first #define se second #define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; using namespace std; int n, m, c[nmax]; vector<pii> adj[nmax]; pii a[nmax]; int ans[nmax], h[nmax], up[nmax][lg + 1]; bool vis[nmax], cc[nmax]; int cost[nmax]; int r[nmax]; int get(int u){ return r[u] ? r[u] = get(r[u]) : u; } void dfs(int u, int p, int W){ cost[u] = W; for(auto [w, v] : adj[u]){ if(v == p) continue; h[v] = h[u] + 1; up[v][0] = u; for(int j = 1; j <= lg; ++j) up[v][j] = up[up[v][j - 1]][j - 1]; dfs(v, u, w); } } int lca(int u, int v){ if(h[u] != h[v]){ if(h[u] < h[v]) swap(u, v); int k = h[u] - h[v]; for(int j = 0;j <= __lg(k); ++j){ if(k >> j & 1){ u = up[u][j]; } } } if(u == v) return u; for(int j = __lg(h[u]); j >= 0; --j){ if(up[u][j] != up[v][j]){ u = up[u][j]; v = up[v][j]; } } return up[u][0]; } int main(){ ios_base::sync_with_stdio(NULL); cin.tie(0);cout.tie(0); // freopen("TRAVEL.inp", "r", stdin); // freopen("TRAVEL.out", "w", stdout); cin >> n >> m; for(int i = 1, u, v; i <= m; ++i){ cin >> u >> v; a[i] = {u, v}; } for(int i = 1, x, u, v; i < n; ++i){ cin >> x; u = a[x].fi, v = a[x].se; adj[u].push_back({x, v}); adj[v].push_back({x, u}); vis[x] = 1; } dfs(1, -1, 0); int cur = 0; vector<int> tmp; for(int i = 1, u, v; i <= m; ++i){ u = a[i].fi, v = a[i].se; if(h[u] < h[v]) swap(u, v); if(ans[i]) continue; if(!vis[i]){ int x = lca(u, v); u = get(u); v = get(v); while(h[u] > h[x]){ int it1 = u; int it2 = get(up[u][0]); r[it1] = it2; tmp.push_back(cost[u]); u = get(u); } while(h[v] > h[x]){ int it1 = v; int it2 = get(up[v][0]); r[it1] = it2; tmp.push_back(cost[v]); v = get(v); } sort(tmp.begin(), tmp.end()); for(auto id : tmp) ans[id] = ++cur; tmp.clear(); ans[i] = ++cur; } else{ ans[i] = ++cur; u = get(u), v = get(v); r[u] = v; } } for(int i = 1; i <= m; ++i) cout << ans[i] << ' '; } /* 4 3 2000 1 2 1050 2 3 1000 2 4 1030 2 1030 1 1020 1 890 */
#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...