Submission #1194668

#TimeUsernameProblemLanguageResultExecution timeMemory
1194668julia_08Railway (BOI17_railway)C++20
0 / 100
84 ms26040 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 10; int marc[MAXN], deg[MAXN], nivel[MAXN]; int dp[20][MAXN]; vector<int> adj[MAXN]; int root = 1, nivel_root = 0; set<int> active, leaf; void dfs(int v, int p){ for(auto u : adj[v]){ if(u != p){ nivel[u] = nivel[v] + 1; dp[0][u] = v; dfs(u, v); } } } int jump(int v){ for(int k=19; k>=0; k--){ if(nivel[dp[k][v]] < nivel_root) continue; if(!active.count(dp[k][v])) v = dp[k][v]; } v = dp[0][v]; return v; } int main(){ cin.tie(0)->sync_with_stdio(0); int n, m, k; cin >> n >> m >> k; vector<pair<int, int>> edges; for(int i=1; i<n; i++){ int a, b; cin >> a >> b; edges.push_back({a, b}); adj[a].push_back(b); adj[b].push_back(a); deg[a] ++; deg[b] ++; } dp[0][root] = 1; dfs(root, root); for(int k=1; k<20; k++){ for(int i=1; i<=n; i++){ dp[k][i] = dp[k - 1][dp[k - 1][i]]; } } for(int i=1; i<=n; i++){ active.insert(i); if(deg[i] == 1) leaf.insert(i); } while(m--){ int s; cin >> s; vector<int> vtx(s); for(int i=0; i<s; i++){ cin >> vtx[i]; if(!active.count(vtx[i])) vtx[i] = jump(vtx[i]); marc[vtx[i]] ++; } queue<int> q; for(auto x : leaf) q.push(x); while(!q.empty()){ int v = q.front(); q.pop(); if(marc[v]) continue; if(v == root) nivel_root ++; leaf.erase(v); active.erase(v); for(auto u : adj[v]){ deg[u] --; if(deg[u] == 1){ leaf.insert(u); q.push(u); } } } for(int i=0; i<s; i++) marc[vtx[i]] --; } cout << (int) active.size() - 1 << "\n"; for(int i=0; i<(int) edges.size(); i++){ if(active.count(edges[i].first) && active.count(edges[i].second)){ cout << i + 1 << " "; } } 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...