Submission #830078

#TimeUsernameProblemLanguageResultExecution timeMemory
830078NK_Rigged Roads (NOI19_riggedroads)C++17
10 / 100
237 ms47688 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define pb push_back #define mp make_pair #define f first #define s second #define sz(x) int(x.size()) template<class T> using V = vector<T>; using vi = V<int>; using ll = long long; using pi = pair<int, int>; using vpi = V<pi>; using vl = V<ll>; using db = long double; const int INF = 1e9 + 10; struct DSU { vi e; void init(int N) { e = vi(N, -1); } int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } void unite(int x, int y) { x = get(x), y = get(y); e[x] += e[y]; e[y] = x; } }; int main() { cin.tie(0)->sync_with_stdio(0); int N, M; cin >> N >> M; vpi E; for(int i = 0; i < M; i++) { int u, v; cin >> u >> v; --u, --v; E.pb(mp(u, v)); } V<vpi> adj(N); vi on(M); for(int i = 0; i < N - 1; i++) { int x; cin >> x; --x; on[x] = 1; auto [u, v] = E[x]; adj[u].pb(mp(v, x)); adj[v].pb(mp(u, x)); } vi par(N), id(N), dep(N); function<void(int)> dfs = [&](int u) { for(auto& e : adj[u]) if (e.f != par[u]) { id[e.f] = e.s; dep[e.f] = dep[u] + 1; par[e.f] = u; dfs(e.f); } }; par[0] = -1, id[0] = -1, dep[0] = 0; dfs(0); vi ans(M, -1); int cur = 1; DSU D; D.init(N); for(int i = 0; i < M; i++) if (!on[i]) { auto [u, v] = E[i]; vi upd; while(1) { int a = D.get(u), b = D.get(v); if (a == b) break; if (dep[a] < dep[b]) swap(a, b); assert(par[a] != -1); D.unite(par[a], a); upd.pb(id[a]); } sort(begin(upd), end(upd)); for(auto x : upd) ans[x] = cur++; ans[i] = cur++; } for(auto &x : ans) { if (x == -1) x = cur++; cout << x << " "; } cout << nl; return 0; }
#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...