Submission #1205901

#TimeUsernameProblemLanguageResultExecution timeMemory
1205901notmeWerewolf (IOI18_werewolf)C++20
0 / 100
760 ms205304 KiB
#include <bits/stdc++.h> #define pb push_back #include "werewolf.h" using namespace std; const int maxn = 4e5 + 10; int n, m, q; vector < int > g[maxn]; struct query { int l, r, s, e; query(){}; query(int _l, int _r, int _s, int _e) { l = _l; r = _r; s = _s; e = _e; } }; /// seg int t[maxn * 4]; int ql, qr; int doquery(int i, int l, int r) { if(qr < l || ql > r)return 0; if(ql <= l && r <= qr)return t[i]; int mid = (l + r)/2; return doquery(2*i, l, mid) + doquery(2*i+1, mid+1, r); } int make_query(int queryl, int queryr) { ql = queryl; qr = queryr; return doquery(1, 1, n); } int updpos, updval; void update(int i, int l, int r) { if(l == r) { t[i] = updval; return; } int mid = (l + r)/2; if(updpos <= mid)update(2*i, l, mid); else update(2*i+1, mid+1, r); t[i] = t[2*i] + t[2*i+1]; } void make_update(int pos, int val) { updpos = pos; updval = val; update(1, 1, n); } query ask[maxn]; vector < int > emax, emin; struct dsu_tree /// mintree -> pref, ends in n-1 { /// maxtree -> suff, ends in 0 int tmr, sz; vector < int > t; vector < int > p; vector < int > tin, tout; vector < vector < int > > adj; vector < int > pos; vector < vector < int > > jump; vector < int > val; dsu_tree(int n) { tmr = 0; p.resize(2*n); /// dsu /// in reconstruction tree t.resize(2*n); adj.resize(2*n); val.resize(2*n); /// later on tin.resize(2*n); tout.resize(2*n); jump.resize(2*n); pos.resize(2*n); for (int i = 0; i < n; ++ i) { p[i] = i; t[i] = i; sz ++; } } /// dsu stuff int find_leader(int i) { if(p[i] == i)return i; return (find_leader(p[i])); } void add_edge(int v, int u, int w) { // cout << "adding edge " << v << " " << u << " with " << w << endl; int leadv = find_leader(v); int leadu = find_leader(u); if(leadv == leadu)return; p[leadu] = leadv; /// v novoto dyrvo u = t[leadu]; v = t[leadv]; t[leadv] = sz; adj[sz].pb(v); adj[sz].pb(u); val[sz] = w; sz ++; } /// euler stuff void euler(int beg, int from, bool type) { if(type == 0) emin.pb(beg); else emax.pb(beg); jump[beg].resize(20); jump[beg][0] = from; for (int j = 1; j < 20; ++ j) { if(jump[beg][j-1] == -1) { jump[beg][j] = -1; continue; } jump[beg][j] = jump[jump[beg][j-1]][j-1]; } if(adj[beg].size() == 0) { tmr ++; tin[beg] = tmr-1; tout[beg] = tmr-1; pos[beg] = tmr-1; return; } tin[beg] = 1e9; tout[beg] = -1; for (auto nb: adj[beg]) { if(nb == from)continue; euler(nb, beg, type); tin[beg] = min(tin[beg], tin[nb]); tout[beg] = max(tout[beg], tout[nb]); } } }; struct segm { int lmax, rmax, lmin, rmin; segm(){}; segm(int _lmax, int _rmax, int _lmin, int _rmin) { lmax = _lmax; rmax = _rmax; lmin = _lmin; rmin = _rmin; } }; std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) { n = N; m = L.size(); q = S.size(); for (int i = 0; i < X.size(); ++ i) { int from = X[i], to = Y[i]; g[from].pb(to); g[to].pb(from); } for (int i = 0; i < m; ++ i) { ask[i] = query(L[i], R[i], S[i], E[i]); } dsu_tree mintree(n), maxtree(n); for (int i = 0; i < n; ++ i) { for (auto j: g[i]) { if(j >= i)continue; mintree.add_edge(i, j, i); } } int szmin = mintree.sz; mintree.euler(szmin-1, -1, 0); for (int i = n-1; i >= 0; -- i) { for (auto j: g[i]) { if(j <= i)continue; maxtree.add_edge(mintree.pos[i], mintree.pos[j], i); } } // int szmin = mintree.sz; int szmax = maxtree.sz; // mintree.euler(szmin-1, -1, 0); maxtree.euler(szmax-1, -1, 1); /* for (int i = 0; i < 2*n; ++ i) cout << mintree.tin[i] << " " << mintree.tout[i] << endl; cout << endl; for (int i = 0; i < 2*n; ++ i) cout << maxtree.tin[i] << " " << maxtree.tout[i] << endl; cout << endl;*/ std::vector < int > ans; vector < segm > sg; ans.resize(q, 0); vector < vector < int > > st, fi; st.resize(2*n+1); fi.resize(2*n+1); for (int i = 0; i < q; ++ i) { int from = mintree.pos[ask[i].s]; int to = ask[i].e; //cout << "* " << from << " " << to << endl; for (int bit = 19; bit >= 0; -- bit) { if(maxtree.jump[from][bit] != -1 && maxtree.val[maxtree.jump[from][bit]] >= ask[i].l) from = maxtree.jump[from][bit]; } for (int bit = 19; bit >= 0; -- bit) { if(mintree.jump[to][bit] != -1 && mintree.val[mintree.jump[to][bit]] <= ask[i].r) to = mintree.jump[to][bit]; } // cout << from << " " << to << endl; // cout << maxtree.tin[from ] << " " << maxtree.tout[from ] << endl; //cout << maxtree.tin[from ] << " " << maxtree.tout[from] << " " << mintree.tin[to] << " " << max sg.pb(segm(maxtree.tin[from], maxtree.tout[from], mintree.tin[to], mintree.tout[to])); } for (int i = 0; i < sg.size(); ++ i) { // cout << sg[i].lmax << " " << sg[i].rmax << " " << sg[i].lmin << " " << sg[i].rmin << endl; int lt = sg[i].lmax, rt = sg[i].rmax; if(lt)fi[lt - 1].pb(i); st[rt].pb(i); } for (int i = 0; i < n; ++ i) { make_update(mintree.pos[i], 1); for (auto &x: fi[i]) { long long num = make_query(sg[x].lmin, sg[x].rmin); ans[x] -= num; } for (auto &x: st[i])ans[x] += make_query(sg[x].lmin, sg[x].rmin); } for (int i = 0; i <ans.size(); ++ i) { if(ans[i] > 0)ans[i] = 1; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...