제출 #395903

#제출 시각아이디문제언어결과실행 시간메모리
395903PetiRailway (BOI17_railway)C++14
100 / 100
137 ms28056 KiB
#include <bits/stdc++.h> using namespace std; const int logn = 20; vector<vector<pair<int, int>>> g; vector<vector<int>> lca; vector<int> h1, h2, ert; vector<bool> volt; int hely = 0; void bejar(int akt, int os){ volt[akt] = true; h1[akt] = hely++; lca[akt][0] = os; for(pair<int, int> e : g[akt]) if(!volt[e.first]) bejar(e.first, akt); h2[akt] = hely++; return; } int get_lca(int a, int b){ if(h1[a] > h1[b]) swap(a, b); if(h1[a] < h1[b] && h2[b] < h2[a]) return a; for(int i = logn-1; i >= 0; i--) if(h2[lca[a][i]] < h2[b]) a = lca[a][i]; return lca[a][0]; } vector<int> ki; int bejar2(int akt, int k, int el){ volt[akt] = true; int ret = ert[akt]; for(pair<int, int> e : g[akt]) if(!volt[e.first]) ret += bejar2(e.first, k, e.second); if(ret >= k) ki.push_back(el); return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin>>n>>m>>k; g.resize(n); h1.resize(n); h2.resize(n); ert.resize(n, 0); volt.assign(n, false); lca.resize(n, vector<int>(logn)); for(int i = 0; i < n-1; i++){ int a, b; cin>>a>>b; g[a-1].emplace_back(b-1, i+1); g[b-1].emplace_back(a-1, i+1); } bejar(0, 0); for(int j = 1; j < logn; j++) for(int i = 0; i < n; i++) lca[i][j] = lca[lca[i][j-1]][j-1]; for(int i = 0; i < m; i++){ int a; cin>>a; vector<int> v(a); for(int &x : v){ cin>>x; x--; } sort(v.begin(), v.end(), [](int a, int b){ return h1[a] < h1[b];}); int ind = -1; if(v.size() > 1) ert[v[0]]++; for(int j = 1; j < (int)v.size(); j++){ int x = get_lca(v[j-1], v[j]); if(ind == -1 || h1[x] < h1[ind]) ind = x; ert[x]--; ert[v[j]]++; } if(ind != -1) ert[ind]--; } volt.assign(n, false); bejar2(0, k, -1); sort(ki.begin(), ki.end()); cout<<ki.size()<<"\n"; for(int x : ki) cout<<x<<" "; 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...