제출 #878123

#제출 시각아이디문제언어결과실행 시간메모리
878123Erfan1386YRailway (BOI17_railway)C++14
29 / 100
69 ms23204 KiB
#include <bits/stdc++.h> #define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout); #define fast_io ios::sync_with_stdio(false);cin.tie(0); #define what(x) cerr << #x << " is " << x << '\n'; #define kill(x) {cout << x << '\n'; return 0;} #define all(x) (x).begin(), (x).end() #define pii pair<int, int> #define pll pair<ll, ll> #define pb push_back #define ll long long #define F first #define S second const ll inf = 1e18, mod = 1e9 + 7, delta = 1e9 + 9, SQ = 450, P = 6065621; using namespace std; const ll N = 1e5 + 10, LG = 20; int h[N], par[N][LG], f[N], cnt[N], k; vector<pii> adj[N]; vector<int> ans; void pre (int v, int p = -1, int e = -1) { par[v][0] = p; f[v] = e; if (p != -1) h[v] = h[p] + 1; for (int i = 1; i < LG; i++) if (par[v][i - 1] != -1) par[v][i] = par[par[v][i - 1]][i - 1]; for (auto u: adj[v]) if (p != u.F) pre(u.F, v, u.S); } int lca (int u, int v) { if (h[u] < h[v]) swap(u, v); for (int i = LG - 1; i >= 0; i--) if (par[u][i] != -1 && h[par[u][i]] >= h[v]) u = par[u][i]; if (u == v) return u; for (int i = LG - 1; i >= 0; i--) if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i]; return par[u][0]; } void dfs (int v, int p = -1) { for (auto u: adj[v]) { if (u.F != p) { dfs(u.F, v); if (cnt[u.F] >= k) { ans.pb(u.S); } cnt[v] += cnt[u.F]; cnt[u.F] = 0; } } } int main() { fast_io; int n, m; cin >> n >> m >> k; memset(par, -1, sizeof par); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].pb({v, i}); adj[v].pb({u, i}); } pre(1); for (int i = 1; i <= m; i++) { int x; cin >> x; vector<int> d(x); for (int j = 0; j < x; j++) cin >> d[j]; int l = lca(d[0], d[1]); cnt[l]--; for (int j = 2; j < x; j++) l = lca(l, d[j]), cnt[l]--; // cnt[l]++; for (auto u: d) cnt[u]++; cnt[l] -= x; } dfs(1); cout << ans.size() << '\n'; sort(all(ans)); for (auto u: ans) cout << u << ' '; 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...