Submission #1036220

#TimeUsernameProblemLanguageResultExecution timeMemory
1036220sinatbtfardRailway (BOI17_railway)C++17
0 / 100
1020 ms23376 KiB
#include <bits/stdc++.h> #define pb push_back using namespace std; const int maxn = 1e5 + 1, maxLg = 20; int n, q, k, timer, cnt, a[maxn], h[maxn], st[maxn], fn[maxn], par[maxn][maxLg]; vector <int> adj[maxn], res; void dfs (int v, int p = 0){ st[v] = timer++; par[v][0] = p; for (int i = 1; i < maxLg; i++) par[v][i] = par[par[v][i - 1]][i - 1]; for (auto u : adj[v]){ if (u != p){ h[u] = h[v] + 1; dfs(u, v); } } fn[v] = timer++; } int lca (int v, int mnst, int mxfn){ for (int i = maxLg - 1; i >= 0; i--){ if (par[v][i] == 0) continue; int u = par[v][i]; if (!(st[u] <= mnst && fn[u] >= mxfn)) v = u; } return par[v][0]; } void dfs2 (int v, int p = 0){ for (auto u : adj[v]) if (u != p) dfs2(u, v); if (adj[v].size() == 1 && v != 1) cnt = 0; if ((cnt += a[v]) >= k) res.pb(v); } int main (){ ios_base::sync_with_stdio(0); cin >> n >> q >> k; for (int x, y, i = 0; i < n - 1; i++) cin >> x >> y, adj[x].pb(y), adj[y].pb(x); dfs(1); int tmp = 1, mnst = 1e8, mxfn = -1; for (int s, i = 0; i < q; i++){ cin >> s; for (int x, i = 0; i < n; i++) cin >> x, a[x]++, tmp = (h[tmp] < h[x] ? x : tmp), mnst = min(mnst, st[x]), mxfn = max(mxfn, fn[x]); a[lca(tmp, mnst, mxfn)] -= s; } dfs2(1); cout << res.size() << '\n'; for (auto ver : res) cout << ver << " "; }
#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...