Submission #515532

#TimeUsernameProblemLanguageResultExecution timeMemory
515532akhan42Railway (BOI17_railway)C++17
36 / 100
369 ms39364 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> using namespace std; //using namespace __gnu_pbds; #define F first #define S second #define forn(i, n) for(int i = 0; i < n; ++i) #define forbn(i, b, n) for(int i = b; i < n; ++i) #define sz(v) (int)v.size() #define pb push_back #define eb emplace_back #define all(v) v.begin(), v.end() #define mp make_pair typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef long long ll; //typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; template <class T> inline void mineq(T &a, T b) { a = min(a, b); } template <class T> inline void maxeq(T &a, T b) { a = max(a, b); } const int MX = 100 * 1000 + 10; const int mxpw = 20; vii tobe_cleaned; struct Seg { int n; vi t; Seg(int n): n(n) { t.assign(2 * n, 0); } void update(int l, int r, bool clean = false, int val = 1) { if(clean) tobe_cleaned.eb(l, r); for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1) { if(l & 1) t[l++] += val; if(r & 1) t[--r] += val; } } int query(int p) { int res = 0; for(p += n; p > 0; p >>= 1) res += t[p]; return res; } }; vi gr[MX]; int timer = 0; int tin[MX], tout[MX]; int par[mxpw][MX]; int sub_sz[MX]; int depth[MX]; int root[MX]; int node2edge[MX]; map<ii, int> edges; void dfs1(int node = 1, int pr = 0, int dep = 0) { depth[node] = dep; par[0][node] = pr; sub_sz[node] = 1; if(pr != 0) node2edge[node] = edges[mp(min(node, pr), max(node, pr))]; for(int &nb: gr[node]) { gr[nb].erase(find(all(gr[nb]), node)); dfs1(nb, node, dep + 1); sub_sz[node] += sub_sz[nb]; if(sub_sz[nb] > sub_sz[gr[node][0]]) swap(nb, gr[node][0]); } } void dfs2(int node = 1) { tin[node] = ++timer; for(int nb: gr[node]) { root[nb] = (gr[node][0] == nb ? root[node] : nb); dfs2(nb); } tout[node] = timer; } Seg* seg_gl; Seg* seg_cur; void process_path(int u, int v, bool upd_gl = true, int val = 1) { for(; root[u] != root[v]; v = par[0][root[v]]) { if(depth[root[u]] > depth[root[v]]) swap(u, v); seg_cur->update(tin[root[v]], tin[v], true); if(upd_gl) seg_gl->update(tin[root[v]], tin[v]); } if(depth[u] > depth[v]) swap(u, v); seg_cur->update(tin[u], tin[v], true); if(upd_gl) seg_gl->update(tin[u], tin[v]); } void clean() { for(ii lr: tobe_cleaned) { int l = lr.F, r = lr.S; seg_cur->update(l, r, false, -1); } tobe_cleaned.clear(); } int lca_node(int u, int v) { for(; root[u] != root[v]; v = par[0][root[v]]) if(depth[root[u]] > depth[root[v]]) swap(u, v); return depth[u] > depth[v] ? v : u; } void solve() { // tout[0] = MX; int n, m, k; cin >> n >> m >> k; forbn(i, 1, n) { int a, b; cin >> a >> b; gr[a].pb(b); gr[b].pb(a); edges[mp(min(a, b), max(a, b))] = i; } seg_gl = new Seg(n + 1); seg_cur = new Seg(n + 1); dfs1(); // root[1] = 1; dfs2(); forbn(d, 1, mxpw) { forn(i, n + 1) { int to = par[d - 1][i]; par[d][i] = par[d - 1][to]; } } forn(i, m) { int s; cin >> s; vi nodes(s); int lca = -1; forn(j, s) { cin >> nodes[j]; if(j == 0) lca = nodes[j]; else lca = lca_node(lca, nodes[j]); } process_path(0, lca, false, 1); forn(j, s) { int u = nodes[j]; if(seg_cur->query(tin[u])) continue; for(int pw = mxpw - 1; pw >= 0; pw--) if(seg_cur->query(tin[par[pw][u]]) == 0) u = par[pw][u]; process_path(nodes[j], u); } clean(); } vi ans; forbn(u, 2, n + 1) { // cerr << u << ' ' << seg_gl->query(tin[u]) << '\n'; if(seg_gl->query(tin[u]) >= k) { ans.pb(node2edge[u]); } } cout << sz(ans) << '\n'; for(int a: ans) { cout << a << ' '; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // freopen("grassplant.in", "r", stdin); // freopen("grassplant.out", "w", stdout); int t = 1; // cin >> t; while(t--) { solve(); } }
#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...