| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1127928 | andrewp | Werewolf (IOI18_werewolf) | C++20 | 0 ms | 0 KiB |
//Dedicated to my love,ivaziva
#include <bits/stdc++.h>
// #include "werewolf.h"
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define vi vector<int>
#define i128 __int128
using namespace std;
const int maxn = 2e5 + 7;
int n, m, q, inv[maxn], lg[maxn], stMin[maxn][20], stMax[maxn][20];
vi g[maxn];
vi a;
struct DSU {
vector<int> p, sz;
void init(int n) {
p.resize(n), sz.resize(n);
L(i, 0, n - 1) {
p[i] = i;
sz[i] = 1;
}
}
int get(int x) {
return x == p[x] ? x : p[x] = get(p[x]);
}
void join(int u, int v) {
u = get(u), v = get(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
p[v] = u;
}
};
void dfs(int x, int par) {
a.pb(x);
for(int u : g[x]) {
if(u != par) {
dfs(u, x);
}
}
}
void Build() {
L(i, 2, n) lg[i] = lg[i >> 1] + 1;
L(i, 1, n) {
stMin[i][0] = a[i - 1];
stMax[i][0] = a[i - 1];
}
L(j, 1, 19) {
for(int i = 1; i + (1 << j) <= n + 1; i++) {
stMin[i][j] = min(stMin[i][j - 1], stMin[i + (1 << (j - 1))][j - 1]);
stMax[i][j] = max(stMin[i][j - 1], stMin[i + (1 << (j - 1))][j - 1]);
}
}
}
int GetMin(int l, int r) {
l++, r++;
int k = lg[r - l + 1];
return min(stMin[l][k], stMin[r - (1 << k) + 1][k]);
}
int GetMax(int l, int r) {
l++, r++;
int k = lg[r - l + 1];
return max(stMax[l][l], stMax[r - (1 << k) + 1][k]);
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L_, vi R_) {
n = N, m = sz(X), q = sz(S);
L(i, 0, m - 1) {
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
vi ans(q, 0);
if(n <= 3000 && m <= 6000 && q <= 3000) {
DSU dsu;
L(i, 0, q - 1) {
int s = S[i], e = E[i], l = L_[i], r = R_[i];
dsu.init(n);
vi cnt(n, 0);
L(x, 0, n - 1) {
for(auto u : g[x]) {
if(u >= l && x >= l) {
dsu.join(x, u);
}
}
}
L(x, 0, n - 1) {
if(dsu.get(x) == dsu.get(s)) cnt[x]++;
}
dsu.init(n);
L(x, 0, n - 1) {
for(auto u : g[x]) {
if(u <= r && x <= r) {
dsu.join(x, u);
}
}
}
L(x, 0, n - 1) {
if(dsu.get(x) == dsu.get(e)) cnt[x]++;
}
L(x, 0, n - 1) {
if(cnt[x] >= 2) {
ans[i] = 1;
}
}
}
} else if(m == n - 1) {
dfs(0, -1);
Build();
L(i, 0, n - 1) inv[a[i]] = i;
L(i, 0, q - 1) {
int s = S[i], e = E[i], l = L_[i], r = R_[i];
int idxS = inv[s], idxE = inv[e];
if(idxS < idxE) {
int bot = idxS, top = idxE, f = -1, s = -1;
while(bot <= top) {
int mid = bot + top >> 1;
if(GetMin(bot, mid) >= l) {
bot = mid + 1;
f = mid;
} else top = mid - 1;
}
bot = idxS, top = idxE;
while(bot <= top) {
int mid = bot + top >> 1;
if(GetMax(mid, top) <= r) {
top = mid - 1;
s = mid;
} else bot = mid + 1;
}
if(f >= s) ans[i] = 1;
} else {
int bot = idxS, top = idxE, f = -1, s = -1;
while(bot <= top) {
int mid = bot + top >> 1;
if(GetMax(bot, mid) >= l) {
bot = mid + 1;
f = mid;
} else top = mid - 1;
}
bot = idxS, top = idxE;
while(bot <= top) {
int mid = bot + top >> 1;
if(GetMin(mid, top) <= r) {
top = mid - 1;
s = mid;
} else bot = mid + 1;
}
if(f >= s) ans[i] = 1;
}
}
}
return ans;
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int N, M, Q;
cin >> N >> M >> Q;
vi X(M), Y(M), S(Q), E(Q), L_(Q), R_(Q);
L(i, 0, M - 1) {
cin >> X[i] >> Y[i];
}
L(i, 0, Q - 1) {
cin >> S[i] >> E[i] >> L_[i] >> R_[i];
}
vi ans = check_validity(N, X, Y, S, E, L_, R_);
L(i, 0, Q - 1) {
cout << ans[i] << ' ';
}
cout << '\n';
return 0;
}