제출 #595274

#제출 시각아이디문제언어결과실행 시간메모리
595274MadokaMagicaFan늑대인간 (IOI18_werewolf)C++17
49 / 100
686 ms81372 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; using vi = vector<int>; #define all(v) v.begin(), v.end() #define sz(v) ((int)v.size()) #define pb push_back #define endl '\n' #define fst first #define scn second const int N = 2e5; const int K = 17; vi adj[N]; struct dsu{ int s[N]; int in[N]; vector<array<int,K>> p; vector<vi> dch; int n; dsu(int _n) { n = _n; p.resize(n); dch.resize(n); for (int i = 0; i < n; ++i) { p[i][0] = i; p[i][1] = i; s[i] = 1; } } int getp(int x) { return p[x][1] = (x == p[x][1]) ? x : getp(p[x][1]) ; } void conc(int a, int b) { b = getp(b); if (a == b) return; dch[a].pb(b); p[b][0] = a; p[b][1] = a; s[a] += s[b]; return; } int dfs(int x, int cnt) { in[x] = cnt++; for(int u : dch[x]) cnt = dfs(u, cnt); return cnt; } void gen() { dfs(n-1,0); for (int j = 1; j < K; ++j) { for (int i = 0; i < n; ++i) { p[i][j] = p[p[i][j-1]][j-1]; } } return; } void query(int& x1, int& x2, int st, int v) { ++v; for (int j = K-1; j >= 0; --j) { if (p[st][j] < v) st = p[st][j]; } x1 = in[st]; x2 = x1 + s[st]-1; return; } }; struct aib{ vi tr; int n; aib(int _n) { n = _n; tr.assign(n,0); } void add(int x, int v) { for(; x < n; x |= (x+1)) tr[x] += v; return; } int query(int x) { int res = 0; for (; x >= 0; x = (x&(x+1))-1) res += tr[x]; return res; } int query(int l, int r) { return query(r) - query(l-1); } }; vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> b, vector<int> e, vector<int> l, vector<int> r) { for (int i = 0; i < sz(x); ++i) { adj[x[i]].pb(y[i]); adj[y[i]].pb(x[i]); } dsu up(n), dn(n); for (int i = 0; i < n; ++i) { for (int u : adj[i]) if (u < i) up.conc(i, u); } for (int i = n-1; i >= 0; --i) { for (int u : adj[i]) if (u > i) dn.conc(n-1-i, n-1-u); } up.gen(); dn.gen(); int q = sz(l); vi ans(q,0); vector<pair<int,int>> in, out; vi y1(q) ,y2(q), pos(n); for (int i = 0; i < q; ++i) { int x1, x2, x3, x4; up.query(x1,x2, e[i], r[i]); dn.query(x3,x4, n-1-b[i], n-1-l[i]); in.pb({x1,i}); out.pb({x2,i}); y1[i] = x3; y2[i] = x4; } sort(in.begin(), in.end()); sort(out.begin(), out.end()); for (int i = 0; i < n; ++i) pos[up.in[i]] = n-i-1; int pi, po; pi = po = 0; aib tr(n); for (int i = 0; i < n; ++i) { while(pi < q) { if (i < in[pi].fst) break; ans[in[pi].scn] -= tr.query(y1[in[pi].scn], y2[in[pi].scn]); ++pi; } tr.add(dn.in[pos[i]],1); while(po < q) { if (i < out[po].fst) break; ans[out[po].scn] += tr.query(y1[out[po].scn], y2[out[po].scn]); ++po; } } for (int i = 0; i < q; ++i) if (ans[i]) ans[i] = 1; return ans; } #ifdef ONPC void solve() { int n, m, q; cin >> n >> m >> q; vector<int> x(m), y(m), s(q), e(q), l(q), r(q); for (int i = 0; i < m; ++i) cin >> x[i]; for (int i = 0; i < m; ++i) cin >> y[i]; for (int i = 0; i < q; ++i) cin >> s[i]; for (int i = 0; i < q; ++i) cin >> e[i]; for (int i = 0; i < q; ++i) cin >> l[i]; for (int i = 0; i < q; ++i) cin >> r[i]; vector<int> ans = check_validity(n,x,y,s,e,l,r); for (int a : ans) { cout << a << ' '; } cout << endl; } int32_t main() { ios_base::sync_with_stdio(0);cin.tie(0); freopen("in", "r", stdin); int t = 1; /* cin >> t; */ while(t--) solve(); } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...