Submission #363742

#TimeUsernameProblemLanguageResultExecution timeMemory
363742shivensinha4Rigged Roads (NOI19_riggedroads)C++17
0 / 100
600 ms262148 KiB
#include "bits/stdc++.h" using namespace std; #define for_(i, s, e) for (int i = s; i < (int) e; i++) #define for__(i, s, e) for (ll i = s; i < e; i++) typedef long long ll; typedef vector<int> vi; typedef array<int, 2> ii; //#define endl '\n' vi depth, tin, ans; vector<ii> tour, edge; vector<vector<ii>> adj; int pt = 1; void dfs(int p) { tin[p] = tour.size(); tour.push_back({depth[p], p}); for (auto &i: adj[p]) if (i[0] != edge[p][0]) { depth[i[0]] = depth[p]+1; edge[i[0]] = {p, i[1]}; dfs(i[0]); tour.push_back({depth[p], p}); } } class SparseTable { vector<vector<ii>> st; int n; void buildTable(vector<ii> &raw) { int k = __lg(n)+1; st.resize(n, vector<ii> (k)); for_(i, 0, n) st[i][0] = raw[i]; for_(p, 1, k+1) for_(i, 0, n - (1<<p) + 1) st[i][p] = min(st[i][p-1], st[i + (1 << (p-1))][p-1]); } public: void build(vector<ii> &nums) { n = nums.size(); buildTable(nums); } int mn(int l, int r) { int p = __lg(r-l+1); return min(st[l][p], st[r - (1<<p) + 1][p])[1]; } }; SparseTable st; class UFDS { public: vi p, rank; int count = 0; void build(int n) { p.resize(n); rank.resize(n); edge.resize(n); for_(i, 0, n) p[i] = i; count = n; } int getParent(int i) { return (p[i] == i) ? i : (p[i] = getParent(p[i])); } void join(int i, int j) { int a = getParent(i), b = getParent(j); if (a == b) return; count -= 1; edge[a] = edge[b] = (depth[edge[a][0]] < depth[edge[b][0]]) ? edge[a] : edge[b]; if (rank[a] > rank[b]) { p[b] = a; } else { p[a] = b; if (rank[a] == rank[b]) rank[b] += 1; } } }; UFDS ufds; void up(int a, int p) { vi path; a = ufds.getParent(a); while (a != ufds.getParent(p)) { path.push_back(edge[a][1]); ufds.join(edge[a][0], a); a = ufds.getParent(a); } sort(path.begin(), path.end()); for (auto i: path) ans[i] = pt++; } int main() { #ifdef mlocal freopen("test.in", "r", stdin); #endif ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; depth.resize(n); tin.resize(n); adj.resize(n); edge.resize(n); ans.resize(m, -1); vector<ii> edges(m); for_(i, 0, m) { cin >> edges[i][0] >> edges[i][1]; edges[i][0] -= 1; edges[i][1] -= 1; } vi req(n-1); vector<bool> marked(m); for_(i, 0, n-1) { cin >> req[i]; req[i] -= 1; marked[req[i]] = true; adj[edges[req[i]][0]].push_back({edges[req[i]][1], req[i]}); adj[edges[req[i]][1]].push_back({edges[req[i]][0], req[i]}); } dfs(0); st.build(tour); ufds.build(n); for_(i, 0, m) { if (marked[i]) { if (ans[i] == -1) { ans[i] = pt++; ufds.join(edges[i][0], edges[i][1]); } } else { int lc = st.mn(edges[i][0], edges[i][1]); up(edges[i][0], lc); up(edges[i][1], lc); ans[i] = pt++; } } for (auto i: ans) cout << i << " "; cout << endl; 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...