제출 #1145691

#제출 시각아이디문제언어결과실행 시간메모리
1145691IssaWerewolf (IOI18_werewolf)C++17
100 / 100
682 ms142280 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ent "\n" const int maxn = 1e6 + 100; const ll INF = (ll)1e18 + 100; const int inf = 1e9 + 100; const ll MOD = 998244353; const int maxl = 20; const ll P = 31; int n; vector<tuple<int, int, int>> g[maxn]; struct asd{ int t; int nxt[maxl][maxn]; vector<int> g[maxn]; int p[maxn], a[maxn]; int tin[maxn], tout[maxn]; void calc(){ for(int i = 1; i <= n; i++){ p[i] = i; } } int get(int v){ if(p[v] == v) return v; return p[v] = get(p[v]); } void join(int a, int b, int c){ a = get(a), b = get(b); if(a == b) return; if((a < b) != c) swap(a, b); // cout << a << ' ' << b << ' ' << c << ent; p[b] = a; g[a].push_back(b); } void dfs(int v){ tin[v] = ++t; a[t] = v; for(int k = 1; k < maxl; k++){ nxt[k][v] = nxt[k-1][nxt[k-1][v]]; } for(int to: g[v]){ nxt[0][to] = v; dfs(to); } tout[v] = t; } } A, B; int d[maxn * 4]; void upd(int i, int x, int v = 1, int tl = 1, int tr = n){ d[v] = max(d[v], x); if(tl < tr){ int mid = (tl + tr) >> 1; if(i <= mid) upd(i, x, v<<1, tl, mid); else upd(i, x, v<<1|1, mid+1, tr); } } int get(int l, int r, int v = 1, int tl = 1, int tr = n){ if(tl > r || tr < l) return 0; if(l <= tl && tr <= r) return d[v]; int mid = (tl + tr) >> 1; return max(get(l, r, v<<1, tl, mid) , get(l, r, v<<1|1, mid+1, tr)); } 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; vector<pii> e; for(int i = 0; i < X.size(); i++){ e.push_back({X[i] + 1, Y[i] + 1}); } sort(e.begin(), e.end(), [](pii a, pii b){ return max(a.first, a.second) < max(b.first, b.second); }); B.calc(); A.calc(); for(auto [a, b]: e) B.join(a, b, 0); sort(e.begin(), e.end(), [](pii a, pii b){ return min(a.first, a.second) > min(b.first, b.second); }); for(auto [a, b]: e) A.join(a, b, 1); A.dfs(1); B.dfs(n); vector<int> ans(S.size(), 0); for(int i = 0; i < S.size(); i++){ int a = S[i] + 1, b = E[i] + 1; L[i]++; R[i]++; for(int k = maxl - 1; k >= 0; k--){ if(A.nxt[k][a] && A.nxt[k][a] >= L[i]){ a = A.nxt[k][a]; } if(B.nxt[k][b] && B.nxt[k][b] <= R[i]){ b = B.nxt[k][b]; } } // cout << a << ' ' << A.tin[a] << ' ' << A.tout[a] << ": "; // for(int i = A.tin[a]; i <= A.tout[a]; i++){ // cout << A.a[i] << ' '; // } cout << ent; // cout << b << ' ' << B.tin[b] << ' ' << B.tout[b] << ": "; // for(int i = B.tin[b]; i <= B.tout[b]; i++){ // cout << B.a[i] << ' '; // } cout << ent; g[A.tout[a]].push_back({a, b, i}); } for(int i = 1; i <= n; i++){ upd(B.tin[A.a[i]], i); for(auto [a, b, id]: g[i]){ if(get(B.tin[b], B.tout[b]) >= A.tin[a]){ ans[id] = 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...