Submission #456306

#TimeUsernameProblemLanguageResultExecution timeMemory
456306arujbansalRigged Roads (NOI19_riggedroads)C++17
10 / 100
364 ms63300 KiB
#include <bits/stdc++.h> using namespace std; void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define rng_seed(x) mt19937 rng(x) #define all(x) (x).begin(), (x).end() #define sz(x) (int) (x).size() // #define int long long struct UFDS { int n; vector<int> info; UFDS() {} UFDS(int _n) { init(_n); } void init(int _n) { n = _n; info.assign(n, -1); } int get(int x) { if (info[x] < 0) return x; return info[x] = get(info[x]); } bool unite(int x, int y) { x = get(x), y = get(y); if (x == y) return false; info[x] += info[y]; info[y] = x; return true; } bool connected(int x, int y) { return get(x) == get(y); } }; const int MXN = 3e5 + 5, INF = 1e9 + 5, MXK = 21; int N, E, timer, available_weight, delta; vector<pair<int, int>> edges; vector<pair<int, int>> adj_keep[MXN]; bool keep[MXN]; int tin[MXN], tout[MXN], binlift_par[MXN][MXK], edge_idx[MXN], ans[MXN]; UFDS covering, cover_check; void dfs(int u, int p) { tin[u] = timer++; for (int j = 1; j < MXK; j++) binlift_par[u][j] = binlift_par[binlift_par[u][j - 1]][j - 1]; for (const auto &[v, idx] : adj_keep[u]) { if (v == p) continue; binlift_par[v][0] = u; edge_idx[v] = idx; dfs(v, u); } tout[u] = timer - 1; } bool is_anc(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } int query_lca(int u, int v) { if (is_anc(u, v)) return u; if (is_anc(v, u)) return v; for (int j = MXK - 1; j >= 0; j--) { int lift = binlift_par[u][j]; if (is_anc(lift, v)) continue; u = lift; } return binlift_par[u][0]; } void mark_path(int u, int v) { int lca = query_lca(u, v); u = cover_check.get(u), v = cover_check.get(v); while (u != lca && is_anc(lca, u)) { cover_check.unite(binlift_par[u][0], u); u = cover_check.get(u); } while (v != lca && is_anc(lca, v)) { cover_check.unite(binlift_par[v][0], v); v = cover_check.get(v); } } void fill_path(int u, int v) { int lca = query_lca(u, v); u = covering.get(u), v = covering.get(v); vector<int> path_edges; while (u != lca && is_anc(lca, u)) { path_edges.push_back(edge_idx[u]); covering.unite(binlift_par[u][0], u); u = covering.get(u); } while (v != lca && is_anc(lca, v)) { path_edges.push_back(edge_idx[v]); covering.unite(binlift_par[v][0], v); v = covering.get(v); } sort(all(path_edges)); for (const auto &idx : path_edges) ans[idx] = available_weight++; } void solve() { cin >> N >> E; edges.resize(E); for (auto &[u, v] : edges) { cin >> u >> v; u--, v--; } covering.init(N); cover_check.init(N); for (int i = 0; i < N - 1; i++) { int idx; cin >> idx; idx--; keep[idx] = true; adj_keep[edges[idx].first].emplace_back(edges[idx].second, idx); adj_keep[edges[idx].second].emplace_back(edges[idx].first, idx); } dfs(0, -1); available_weight = 1; for (int i = 0; i < E; i++) if (!keep[i]) mark_path(edges[i].first, edges[i].second); for (int i = 0; i < E; i++) { if (keep[i]) continue; // if (keep[i] && !cover_check.connected(edges[i].first, edges[i].second)) { // ans[i] = available_weight++; // continue; // } fill_path(edges[i].first, edges[i].second); ans[i] += available_weight++; } for (int i = 0, mx = 0, delta = 0; i < E; i++) { if (ans[i] == 0) { ans[i] = ++mx; delta++; } else ans[i] += delta; mx = max(mx, ans[i]); cout << ans[i] << " "; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int TC = 1; // cin >> TC; while (TC--) solve(); }
#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...