Submission #1260635

#TimeUsernameProblemLanguageResultExecution timeMemory
1260635duonggsimpRailway (BOI17_railway)C++20
0 / 100
117 ms48000 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> ii; typedef pair<ii, ll> iii; #define pb push_back #define fi first #define se second #define endl '\n' #define MASK(i) (1ll << (i)) #define BIT(x, i) (((x) >> (i)) & 1) const ll MOD = 1e9+7; ll n,q,k; ll cnt; ll h[100005]; ll par[100005][20]; ll adj[100005]; ll st[100005]; ll f[100005]; vector <ii> res; vector <ll> a[100005]; map <ii,ll> mp; bool cmp(ll a,ll b){ return st[a] < st[b]; } void dfs(ll x,ll p){ st[x] = ++cnt; for (ll i : a[x]){ if (i == p) continue; h[i] = h[x] + 1; par[i][0] = x; dfs(i,x); } } void setup(){ for (long j=1; j<=18; j++){ for (long i=1; i<=n; i++) par[i][j] = par[par[i][j-1]][j-1]; } h[0] = -1; } ll lck(ll u,ll v){ if (h[u] < h[v]) swap(u,v); for (long i=18; i>=0; i--){ if (h[par[u][i]] >= h[v]) u = par[u][i]; } if (u == v) return u; for (long i=18; i>=0; i--){ if (par[u][i] != par[v][i]){ u = par[u][i]; v = par[v][i]; } } return par[u][0]; } void dfs2(ll x,ll p){ for (ll i : a[x]){ if (i == p) continue; dfs2(i,x); f[x] += f[i]; } if (f[x] >= 2 * k) res.pb({x,par[x][0]}); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q >> k; for (long i=1; i<n; i++){ ll u,v; cin >> u >> v; a[u].pb(v); a[v].pb(u); mp[{u,v}] = mp[{v,u}] = i; } h[1] = 1; dfs(1,0); setup(); while (q--){ ll ski; cin >> ski; for (long i=1; i<=ski; i++) cin >> adj[i]; sort(adj+1,adj+ski+1,cmp); adj[ski+1] = adj[1]; for (long i=2; i<=ski+1; i++){ ll x = adj[i-1]; ll y = adj[i]; f[x]++; f[y]++; f[lck(x,y)] -= 2; } } dfs2(1,0); cout << res.size() << endl; for (ii i : res){ ll x = i.fi; ll y = i.se; cout << mp[{i.fi,i.se}] << ' '; } }
#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...