Submission #917482

#TimeUsernameProblemLanguageResultExecution timeMemory
917482406Rigged Roads (NOI19_riggedroads)C++17
40 / 100
298 ms70852 KiB
#include <bits/stdc++.h> #define int int64_t #define FOR(i, a, b) for (int i = (a); i < (b); ++i) using namespace std; using ar = array<int, 2>; const int64_t INF = 1ll << 60; const int N = 3e5 + 5; namespace dsu { int dpr[N]; int gpr(int x) { return dpr[x] == x ? x : dpr[x] = gpr(dpr[x]); } void merge(int u, int v) { dpr[gpr(u)] = gpr(v); } } int st[N], fn[N], T, pr[N], up[N], mn[N], W[N], n, m; ar E[N]; bool ok[N]; vector<int> ad[N]; vector<ar> adj[N]; bool is_p(int p, int v) { return st[p] <= st[v] && fn[v] <= fn[p]; } void dfs(int v) { st[v] = T++; for (auto [u, id]: adj[v]) if (u != pr[v]) { up[u] = id; pr[u] = v; dfs(u); } fn[v] = T; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; FOR(i, 0, m) { cin >> E[i][0] >> E[i][1]; --E[i][0], --E[i][1]; } FOR(i, 1, n) { int x; cin >> x; --x; auto [u, v] = E[x]; adj[v].push_back({u, x}); adj[u].push_back({v, x}); ok[x] = true; } fill(mn, mn + n, n); iota(dsu::dpr, dsu::dpr + n, 0); up[0] = -1; dfs(0); FOR(i, 0, m) if (!ok[i]) { auto [u, v] = E[i]; int tu = dsu::gpr(u), tv = dsu::gpr(v); while (!is_p(tu, v)) { assert(up[tu] != -1); mn[up[tu]] = i; dsu::merge(tu, pr[tu]); tu = dsu::gpr(tu); } while (!is_p(tv, u)) { assert(up[tv] != -1); mn[up[tv]] = i; dsu::merge(tv, pr[tv]); tv = dsu::gpr(tv); } } for (int i = m - 1; i >= 0; --i) if (ok[i]) ad[mn[i]].push_back(i); int r = m; for (int i = m - 1; i >= 0; --i) { if (!ok[i]) { W[i] = r--; for (auto t: ad[i]) if (t > i) W[t] = r--; } else if (mn[i] > i) W[i] = r--; } FOR(i, 0, m) cout << W[i] << ' '; cout << '\n'; 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...