Submission #1213258

#TimeUsernameProblemLanguageResultExecution timeMemory
1213258MalixRailway (BOI17_railway)C++20
7 / 100
85 ms25284 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<int,int,int> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) ll INF=1000000000000000010; int inf=1e9+10; ll M=1e9+7; int n,q,k,m; vector<vector<pi>> a; vector<pi> p; vi num,cnt,low; vii par; int nm=0,lw=0; void dfs(int x){ num[x]=nm++; for(auto [u,v]:a[x])if(p[x].F!=u){ par[u][0]=x; p[u]={x,v}; dfs(u); } low[x]=lw++; } void dfs2(int x){ for(auto [u,v]:a[x])if(p[x].F!=u){ dfs2(u); cnt[x]+=cnt[u]; } } bool ances(int x,int y){ if(y==-1)return 1; if(x==-1)return 0; return (num[x]>=num[y]&&low[x]<=low[y]); } int LCA(int x,int y){ if(ances(x,y))return y; if(ances(y,x))return x; for(int i=m-1;i>=0;i--)if(!ances(x,par[y][i]))x=par[y][i]; return par[y][0]; } int main() { // ios::sync_with_stdio(0); // cin.tie(0); cin>>n>>q>>k; m=log2(n)+1; a.resize(n);p.resize(n,{-1,-1});num.resize(n);low.resize(n); par.resize(n,vi(m,-1)); cnt.resize(n,0); REP(i,0,n-1){ int x,y;cin>>x>>y; x--;y--; a[x].PB({y,i}); a[y].PB({x,i}); } dfs(0); REP(j,1,m)REP(i,0,n)if(par[i][j-1]!=-1)par[i][j]=par[par[i][j-1]][j-1]; while(q--){ int sz;cin>>sz; vector<pi> arr; REP(i,0,sz){ int y;cin>>y; y--; arr.PB({num[y],y}); } sort(arr.begin(),arr.end()); arr.erase(unique(arr.begin(),arr.end()),arr.end()); reverse(arr.begin(),arr.end()); sz=arr.size(); REP(i,0,sz){ int x=arr[i].S,y=arr[(i+1)%sz].S; int z=LCA(x,y); cnt[x]++; cnt[z]--; } } dfs2(0); vi ans; REP(i,1,n)if(cnt[i]>=k)ans.PB(p[i].S); sort(ans.begin(),ans.end()); cout<<ans.size()<<"\n"; for(auto u:ans)cout<<u+1<<" "; }
#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...