제출 #536693

#제출 시각아이디문제언어결과실행 시간메모리
536693__VariattoRailway (BOI17_railway)C++17
36 / 100
128 ms25668 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define ll long long const int MAX=1e5+10, L=18; int n, m, k, jump[MAX][L+2], gle[MAX], pre[MAX]; vector<pair<int,int>>g[MAX], akt; int czas=1; void dfs(int v, int oj){ jump[v][0]=oj; pre[v]=czas++; for(int i=1; i<=L; i++) jump[v][i]=jump[jump[v][i-1]][i-1]; for(auto s:g[v]){ if(s.fi!=oj){ gle[s.fi]=gle[v]+1; dfs(s.fi, v); } } } int LCA(int a, int b){ if(gle[b]>gle[a]) swap(a, b); for(int i=L; i>=0; i--) if(gle[jump[a][i]]>=gle[b]) a=jump[a][i]; if(a==b) return a; int wyn=a; for(int i=L; i>=0; i--){ if(jump[a][i]==jump[b][i]) wyn=jump[a][i]; else a=jump[a][i], b=jump[b][i]; } return wyn; } int dod[MAX], usu[MAX], suma[MAX]; vector<int>wynik; void dfs2(int v, int oj, int ind){ for(auto s:g[v]){ if(s.fi!=oj){ dfs2(s.fi, v, s.se); suma[v]+=suma[s.fi]; } } suma[v]+=dod[v]-usu[v]; if(suma[v]>=k) wynik.pb(ind); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin>>n>>m>>k; for(int i=1; i<=n-1; i++){ int a, b; cin>>a>>b; g[a].pb({b, i}), g[b].pb({a, i}); } dfs(1, 1); for(int i=1; i<=m; i++){ int s, x; cin>>s; akt.clear(); for(int j=1; j<=s; j++){ cin>>x; akt.pb({pre[x], x}); } sort(akt.begin(), akt.end()); int last=0; for(auto a: akt){ if(last){ int lca=LCA(last, a.se); dod[last]++, dod[a.se]++, usu[lca]+=2; } last=a.se; } } dfs2(1, 1, 0); cout<<wynik.size()<<"\n"; sort(wynik.begin(), wynik.end()); for(auto a:wynik) cout<<a<<" "; cout<<"\n"; }
#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...