Submission #714680

#TimeUsernameProblemLanguageResultExecution timeMemory
714680Melika0ghRailway (BOI17_railway)C++17
100 / 100
144 ms27964 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define sync ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define pb push_back #define mp make_pair #define fi first #define se second const int maxn = 2e5 + 10, mood = 1e9 + 7, maxsq = 400, maxlg = 21; //const int mood2 = 97277821, mood3 = 34098487, base = 31; vector<int> adj[maxn]; vector<pair<int, int> > edge; int anc[maxn][maxlg]; int st[maxn], ft[maxn], cnt[maxn], h[maxn]; int n, m, k, t; void Dfs(int v = 1, int par = -1) { st[v] = ++t; for(int i = 1; i < maxlg; i++) { anc[v][i] = anc[anc[v][i-1]][i-1]; } for(auto u : adj[v]) if(u != par) { h[u] = h[v] + 1; anc[u][0] = v; Dfs(u, v); } ft[v] = t; } void Dfs2(int v = 1, int par = -1) { for(auto u : adj[v]) if(u != par) { Dfs2(u, v); cnt[v] += cnt[u]; } return; } int Up(int u, int d) { for(int i = 0; i < maxlg; i++) { if((d >> i) & 1) u = anc[u][i]; } return u; } int Lca(int u, int v) { if(h[u] < h[v]) swap(u, v); u = Up(u, h[u] - h[v]); for(int i = maxlg - 1; i >= 0; i--) { if(anc[u][i] != anc[v][i]) { u = anc[u][i]; v = anc[v][i]; } } if(v == u) return v; return anc[v][0]; } bool cmp(int a, int b) { return st[a] < st[b]; } int main() { sync; cin >> n >> m >> k; for(int i = 0; i < n-1; i++) { int u, v; cin >> u >> v; edge.pb(mp(u, v)); adj[u].pb(v); adj[v].pb(u); } Dfs(); for(int i = 0; i < m; i++) { vector<int> vec; int s; cin >> s; for(int j = 0; j < s; j++) { int x; cin >> x; vec.pb(x); } sort(vec.begin(), vec.end(), cmp); for(int j = 0; j < (int)vec.size(); j++) { int v = vec[j], u = vec[(j+1) % s]; cnt[v]++; int lca = Lca(v, u); cnt[lca]--; } } Dfs2(); vector<int> ans; for(int i = 0; i < n-1; i++) { int u = edge[i].fi, v = edge[i].se; if(h[u] < h[v]) swap(u, v); if(cnt[u] >= k) { ans.pb(i+1); } } cout << (int)ans.size() << '\n'; for(int x : ans) 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...