Submission #463807

#TimeUsernameProblemLanguageResultExecution timeMemory
463807xyzyzlRailway (BOI17_railway)C++14
0 / 100
213 ms23228 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; #define bitinc(x) x&-x int n, m, k; vector<int> adj[MAXN]; int par[100005][20]; int tmp = 0, in[200005], ot[200005], bit[200005]; int sum(int ind) { int sm = 0; while(ind > 0) { sm += bit[ind]; ind -= bitinc(ind); } return sm; } void upd(int ind, int val) { while(ind <= n) { bit[ind] += val; ind += bitinc(ind); } } vector<pair<int, int> > eg; void dfs(int v, int p) { in[v] = ++tmp; par[v][0] = p; for(int i = 1; i < 20; i++) par[v][i] = par[par[v][i-1]][i-1]; for(int x : adj[v]) { if(x == p) continue; dfs(x,v); } ot[v] = ++tmp; } bool anc(int u, int v) { return (in[u] <= in[v] && ot[u] >= ot[v]); } // method finding all lca's int lca(int u, int v) { if(anc(u,v)) return u; for(int i = 19; i >= 0; i--) { // as a verifier make sure par[u][i] >= 0 s.t. no array out of bounds if(par[u][i] >= 0 && !anc(par[u][i], v)) u = par[u][i]; } return par[u][0]; } bool comp(int a, int b) { return in[a] < in[b]; } int main() { cin >> n >> m >> k; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; --u; --v; adj[u].push_back(v); adj[v].push_back(u); eg.push_back({u,v}); } dfs(0, 0); for(int i = 0; i < m; i++) { int s; cin >> s; vector<int> v; for(int i = 0; i < s; i++) { int w; cin >> w; --w; v.push_back(w); } sort(v.begin(), v.end(), comp); for(int i = 0; i < s; i++) { int a = v[i]; int b = v[(i+1)%s]; int c = lca(v[i], v[(i+1)%s]); upd(in[a], 1); upd(in[b], 1); upd(in[c], -2); } } vector<int> ans; for(int i = 0; i < n-1; i++) { pair<int, int> p = eg[i]; if(in[p.first] > in[p.second]) swap(p.first, p.second); int ret = sum(ot[p.second]) - sum(in[p.second]-1); if(ret >= 2*k) ans.push_back(i+1); } cout << ans.size() << endl; for(int x : ans) cout << x << " "; cout << endl; }
#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...