| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1198250 | dubabuba | 늑대인간 (IOI18_werewolf) | C++20 | 0 ms | 0 KiB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define MP make_pair
const int mxn = 2e5;
int n, m, q;
int Hans[mxn], Wans[mxn];
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef bitset<mxn> bi;
bi hun[mxn], dog[mxn];
struct Tree {
int anc[mxn * 2], cnt;
vector<int> chi[mxn * 2];
vector<int> query[mxn * 2];
Tree() { memset(anc, -1, sizeof anc); }
int ancestor(int u) { return anc[u] < 0 ? u : anc[u] = ancestor(anc[u]); }
int unite(int u, int v) {
u = ancestor(u);
v = ancestor(v);
if(u == v) return -1;
anc[cnt] += anc[u];
anc[cnt] += anc[v];
anc[u] = cnt;
anc[v] = cnt;
chi[cnt].push_back(u);
chi[cnt].push_back(v);
return cnt++;
}
bi dfs(int u, bool flag) {
if(u < n) {
bi ret = 0;
ret[u] = 1;
if(flag) {
for(int i : query[u])
hun[i] = ret;
}
else {
for(int i : query[u])
dog[i] = ret;
}
return ret;
}
bi ret = 0;
for(int v : chi[u])
ret |= dfs(v, flag);
if(flag) {
for(int i : query[u])
hun[i] = ret;
}
else {
for(int i : query[u])
dog[i] = ret;
}
return ret;
}
};
Tree humans, wolves;
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
n = N;
m = X.size();
q = S.size();
vector<pii> HQ[n];
vector<pii> WQ[n];
for(int i = 0; i < m; i++) {
int mn = min(X[i], Y[i]);
int mx = max(X[i], Y[i]);
HQ[mn].push_back(MP(-1, mx));
WQ[mx].push_back(MP(-1, mn));
}
for(int i = 0; i < q; i++) {
int l = L[i], r = R[i];
HQ[l].push_back(MP(i, S[i]));
WQ[r].push_back(MP(i, E[i]));
}
// cout << "\nWolves\n";
wolves.cnt = n;
for(int u = 0; u < n; u++) {
for(pii p : WQ[u]) {
int i = p.ff;
int v = p.ss;
if(i == -1) {
int a = wolves.unite(u, v);
// cout << u << ' ' << v << " -> " << a << endl;
}
else {
Wans[i] = wolves.ancestor(v);
wolves.query[Wans[i]].push_back(i);
// cout << "query " << i << ": " << u << ' ' << v << " = " << Wans[i] << endl;
}
}
}
// cout << "\nHumans\n";
humans.cnt = n;
for(int u = n - 1; u >= 0; u--) {
for(pii p : HQ[u]) {
int i = p.ff;
int v = p.ss;
if(i == -1) {
int a = humans.unite(u, v);
// cout << u << ' ' << v << " -> " << a << endl;
}
else {
Hans[i] = humans.ancestor(v);
humans.query[Hans[i]].push_back(i);
// cout << "query " << i << ": " << u << ' ' << n - 1 << " = " << Hans[i] << endl;
}
}
}
bool vis[n * 2];
memset(vis, 0, sizeof vis);
for(int i = 0; i < n; i++) {
int a = wolves.ancestor(i);
if(!vis[a]) {
wolves.dfs(a, 1);
}
}
memset(vis, 0, sizeof vis);
for(int i = 0; i < n; i++) {
int a = humans.ancestor(i);
if(!vis[a]) {
humans.dfs(a, 0);
}
}
vi ret;
bi buba = 0;
for(int i = 0; i < q; i++) {
buba = hun[i] & dog[i];
// cout << S[i] << " -> " << L[i] << ' ' << R[i] << ": ";
// for(int k = 0; k < n; k++)
// cout << hun[i][k];
// cout << endl;
// cout << E[i] << " -> " << L[i] << ' ' << R[i] << ": ";
// for(int k = 0; k < n; k++)
// cout << dog[i][k];
// cout << endl;
if(buba.count())
ret.push_back(1);
else
ret.push_back(0);
// cout << endl;
}
return ret;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/