제출 #568542

#제출 시각아이디문제언어결과실행 시간메모리
568542ngpin04늑대인간 (IOI18_werewolf)C++17
0 / 100
420 ms54724 KiB
#include "werewolf.h" #include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define TASK "" #define bit(x) (1LL << (x)) #define getbit(x, i) (((x) >> (i)) & 1) #define ALL(x) (x).begin(), (x).end() using namespace std; template <typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maxi(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return l + rd() % (r - l + 1); } const int N = 4e5 + 5; const int oo = 1e9; const long long ooo = 1e18; const int mod = 1e9 + 7; // 998244353; const long double pi = acos(-1); struct DSU { bool rev; int n; vector <int> par,val; DSU(int _n = 0, bool _rev = 0) { rev = _rev; n = _n; par.assign(n + 5, -1); val.assign(n + 5, 0); iota(ALL(val), 0); } int getpar(int u) { return (par[u] < 0) ? u : (par[u] = getpar(par[u])); } void join(int u, int v) { u = getpar(u); v = getpar(v); if (par[u] > par[v]) swap(u, v); if (u == v) return; par[u] += par[v]; par[v] = u; if (!rev) maxi(val[u], val[v]); else mini(val[u], val[v]); } int getval(int u) { return val[getpar(u)]; } }; vector <int> ed[N]; vector <int> qr[N]; int par[N]; int ans[N]; int mx[N]; int x[N]; int y[N]; int s[N]; int t[N]; int l[N]; int r[N]; int n,q; void fix() { for (int i = 0; i < n; i++) ed[i].clear(), qr[i].clear(); for (int i = 0; i < n - 1; i++) ed[y[i]].push_back(x[i]); for (int i = 0; i < q; i++) qr[r[i]].push_back(i); DSU pre(n, 0); for (int i = 0; i < n; i++) { for (int j : ed[i]) pre.join(i, j); for (int ind : qr[i]) t[ind] = pre.getval(t[ind]); } for (int i = 0; i < n; i++) ed[i].clear(), qr[i].clear(); for (int i = 0; i < n - 1; i++) ed[x[i]].push_back(y[i]); for (int i = 0; i < q; i++) qr[l[i]].push_back(i); DSU suf(n, 1); for (int i = n - 1; i >= 0; i--) { for (int j : ed[i]) suf.join(i, j); for (int ind : qr[i]) s[ind] = suf.getval(s[ind]); } } void getans() { for (int i = 0; i < n; i++) ed[i].clear(), qr[i].clear(); for (int i = 0; i < n - 1; i++) ed[y[i]].push_back(x[i]); for (int i = 0; i < q; i++) qr[r[i]].push_back(i); DSU pre(n, 0); for (int i = 0; i < n; i++) { for (int j : ed[i]) pre.join(i, j); for (int ind : qr[i]) { if (t[ind] < l[ind] || s[ind] > r[ind]) continue; ans[ind] |= pre.getpar(t[ind]) == pre.getpar(s[ind]); } } for (int i = 0; i < n; i++) ed[i].clear(), qr[i].clear(); for (int i = 0; i < n - 1; i++) ed[x[i]].push_back(y[i]); for (int i = 0; i < q; i++) qr[l[i]].push_back(i); DSU suf(n, 1); for (int i = n - 1; i >= 0; i--) { for (int j : ed[i]) suf.join(i, j); for (int ind : qr[i]) { if (t[ind] < l[ind] || s[ind] > r[ind]) continue; ans[ind] |= suf.getpar(t[ind]) == suf.getpar(s[ind]); } } } void solve() { for (int i = 0; i < n - 1; i++) if (x[i] > y[i]) swap(x[i], y[i]); fix(); getans(); } vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { n = N; for (int i = 0; i < n - 1; i++) x[i] = X[i], y[i] = Y[i]; q = S.size(); for (int i = 0; i < q; i++) { s[i] = S[i]; t[i] = E[i]; l[i] = L[i]; r[i] = R[i]; } solve(); vector <int> res; for (int i = 0; i < q; i++) res.push_back(ans[i]); return res; } //#include "grader.cpp"
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...