제출 #987816

#제출 시각아이디문제언어결과실행 시간메모리
987816AcanikolicRailway (BOI17_railway)C++14
0 / 100
1088 ms26192 KiB
#include <bits/stdc++.h> #define pb push_back #define S second #define F first const int N = 1e5 + 10; const int inf = 2e9; const int lg = 17; using namespace std; vector<int>g[N]; int in[N],out[N],timer = 0,up[N][lg],n,f[N]; void dfs(int x,int par) { in[x] = ++timer; up[x][0] = par; for(int j = 1; j < lg; j++) for(int i = 1; i <= n; i++) up[i][j] = up[up[i][j - 1]][j - 1]; for(auto X : g[x]) { if(X == par) continue; dfs(X,x); } out[x] = timer; } void DFS(int x,int par) { for(auto X : g[x]) { if(X == par) continue; DFS(X,x); f[x] += f[X]; } } bool intree(int u,int v) { return (in[u] <= in[v] && out[u] >= out[v]); } int lca(int u,int v) { if(intree(u,v)) return u; if(intree(v,u)) return v; for(int j = lg - 1; j >= 0; j--) { if(up[u][j] > 0 && !intree(up[u][j],v)) u = up[u][j]; } return up[u][0]; } bool cmp(int A,int B) { return (in[A] <= in[B]); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int m,k; cin >> n >> m >> k; map<pair<int,int>,int>index; for(int i = 1; i < n; i++) { int u,v; cin >> u >> v; index[{u,v}] = i; index[{v,u}] = i; g[u].pb(v); g[v].pb(u); } dfs(1,0); for(int q = 1; q <= m; q++) { int s; cin >> s; vector<int>b; for(int i = 0; i < s; i++) { int x; cin >> x; b.pb(x); } sort(b.begin(),b.end(),cmp); b.pb(b[0]); for(int i = 0; i < s; i++) { f[b[i]] += 1; f[b[i + 1]] += 1; f[lca(b[i],b[i + 1])] -= 2; } } DFS(1,0); vector<int>ans; for(int i = 1; i <= n; i++) { if(f[i] >= k * 2) { ans.push_back(index[{i,up[i][0]}]); } } sort(ans.begin(),ans.end()); cout << ans.size() << "\n"; for(auto X : ans) cout << X << " "; 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...