제출 #666719

#제출 시각아이디문제언어결과실행 시간메모리
666719Eae02Railway (BOI17_railway)C++17
29 / 100
146 ms20424 KiB
#include <bits/stdc++.h> #define all(x) begin(x),end(x) using namespace std; using ll = long long; struct HLD { vector<ll> depth, parent, arridx, hpLeaf, hpRoot, hchild; HLD(const vector<vector<ll>>& t) { // t is an adjacency list, or a child list for a tree rooted in node 0 parent = hchild = vector<ll>(t.size(), -1); depth = arridx = hpLeaf = hpRoot = vector<ll>(t.size()); vector<ll> sts(t.size(), 1), ci(t.size()), st{0}, trav{0}; while (!st.empty()) { ll cur = st.back(), nx; if (ci[cur] == (ll)t[cur].size()) { st.pop_back(); if (st.empty()) continue; sts[st.back()] += sts[cur]; if (hchild[st.back()] == -1 || sts[cur] > sts[hchild[st.back()]]) hchild[st.back()] = cur; } else if ((nx = t[cur][ci[cur]++]) != parent[cur]) { depth[nx] = depth[cur] + 1; parent[nx] = cur; st.push_back(nx); trav.push_back(nx); } } iota(all(hpRoot), 0); iota(all(hpLeaf), 0); ll nai = 0; for (ll cur : trav) { if (hchild[cur] == -1) { arridx[cur] = nai; nai += depth[cur] - depth[hpRoot[cur]] + 1; } else hpRoot[hchild[cur]] = hpRoot[cur]; } for (ll i = trav.size() - 1; i >= 0; i--) { if (hchild[trav[i]] == -1) continue; arridx[trav[i]] = arridx[hchild[trav[i]]] + 1; hpLeaf[trav[i]] = hpLeaf[hchild[trav[i]]]; } } ll lca(ll a, ll b, vector<pair<ll, ll>>* llv = nullptr, bool llvIncludeLCA = true) { auto sdepth = [&] (ll i) { return i == -1 ? -1 : depth[i]; }; auto addi = [&] (ll lo, ll hi) { if (llv && lo != hi) llv->emplace_back(lo, hi); }; while (hpRoot[a] != hpRoot[b]) { ll nxa = parent[hpRoot[a]]; ll nxb = parent[hpRoot[b]]; if (sdepth(nxa) > sdepth(nxb)) { addi(arridx[a], arridx[hpRoot[a]] + 1); a = nxa; } else { addi(arridx[b], arridx[hpRoot[b]] + 1); b = nxb; } } if (depth[a] > depth[b]) swap(a, b); addi(arridx[b], arridx[a] + llvIncludeLCA); return a; } }; int main() { ll numNodes, numMinist, reqMinist; cin >> numNodes >> numMinist >> reqMinist; vector<vector<ll>> adj(numNodes); adj.resize(numNodes); map<pair<ll, ll>, ll> trackIds; for (ll i = 0; i < numNodes - 1; i++) { ll a, b; cin >> a >> b; a--; b--; trackIds.emplace(make_pair(min(a, b), max(a, b)), i+1); adj[a].push_back(b); adj[b].push_back(a); } HLD hld(adj); vector<ll> v(numNodes + 1); for (ll i = 0; i < numMinist; i++) { ll s, sel0; cin >> s >> sel0; if (s == 2) { ll sel1; cin >> sel1; vector<pair<ll, ll>> intv; hld.lca(sel0-1, sel1-1, &intv, false); for (auto [lo, hi] : intv) { v[lo]++; v[hi]--; } } else { return 1; vector<pair<ll, ll>> pts; for (ll j = 1; j < s; j++) { ll node; cin >> node; vector<pair<ll, ll>> intv; hld.lca(sel0-1, node-1, &intv, false); for (auto [lo, hi] : intv) { pts.emplace_back(lo, 1); pts.emplace_back(hi, -1); } } sort(all(pts)); ll depth = 0; for (auto [x, d] : pts) { if (depth == 0) v[x]++; depth += d; if (depth == 0) v[x]--; } } } vector<ll> vps(numNodes + 1); for (ll i = 0; i < numNodes; i++) vps[i+1] = vps[i] + v[i]; vector<ll> reqTracks; for (ll i = 1; i < numNodes; i++) { if (vps[hld.arridx[i]+1] >= reqMinist) { ll p = hld.parent[i]; reqTracks.push_back(trackIds[{min(i, p), max(i, p)}]); } } sort(reqTracks.begin(), reqTracks.end()); cout << reqTracks.size() << "\n"; for (ll t : reqTracks) { cout << t << " "; } cout << "\n"; }
#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...