| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1192398 | nguyn | Werewolf (IOI18_werewolf) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int,int>
const int N = 2e5 + 5;
struct Edge {
int u, v, w;
Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
bool operator < (const Edge &o) const {
return w < o.w;
}
};
vector<Edge> edges;
vector<int> g[2 * N];
struct DSU {
int n;
vector<int> par;
DSU() {}
DSU(int n) : n(n) {
par.resize(n);
for (int i = 0; i < n; i++) par[i] = i;
}
int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
void join(int x, int y) {
if ((x = find(x)) == (y = find(y))) return;
par.emplace_back();
par[y] = par[x] = par[n] = n;
g[n].pb(x);
g[n].pb(y);
// cout << n << ' ' << x << endl;
// cout << n << ' ' << y << endl;
n++;
}
} dsu;
int n, m, q;
int pos[2 * N];
int st[2 * N];
int en[2 * N];
int st1[2 * N];
int en1[2 * N];
int up[2 * N][20];
int a[2 * N];
pii range1[N];
pii range2[N];
int timedfs;
vector<pii> event[2 * N];
void dfs(int u, int p, int type) {
st[u] = ++timedfs;
a[u] = u;
if (type) {
if (u >= n) a[u] = 0;
}
for (int v : g[u]) {
if (v == p) continue;
up[v][0] = u;
for (int i = 1; i < 20; i++) {
if (up[v][i - 1] != -1) up[v][i] = up[up[v][i - 1]][i - 1];
}
dfs(v, u, type);
if (!type) a[u] = min(a[u], a[v]);
else a[u] = max(a[u], a[v]);
}
// cout << u << ' ' << a[u] << endl;
en[u] = timedfs;
}
int jump(int u, int bound, int type) {
if (type == 0) {
for (int i = 19; i >= 0; i--) {
if (up[u][i] != -1 && a[up[u][i]] >= bound) {
u = up[u][i];
}
}
return u;
}
else {
for (int i = 19; i >= 0; i--) {
if (up[u][i] != -1 && a[up[u][i]] <= bound) {
u = up[u][i];
}
}
return u;
}
}
int bit[2 * N];
void update(int id, int val) {
if (id == 0) return;
for (int i = id; i < 2 * n; i += (i & -i)) bit[i] += val;
}
int get(int id) {
int res = 0;
for (int i = id; i > 0; i -= (i & -i)) res += bit[i];
return res;
}
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;
m = X.size();
q = S.size();
dsu = DSU(n);
for (int i = 0; i < m; i++) {
if (X[i] < Y[i]) swap(X[i], Y[i]);
edges.emplace_back(X[i], Y[i], Y[i]);
}
sort(edges.begin(), edges.end());
for (int i = m - 1; i >= 0; i--) {
dsu.join(edges[i].u, edges[i].v);
}
int root = dsu.n;
memset(up, -1, sizeof(up));
dfs(root - 1, -1, 0);
for (int i = 0; i < q; i++) {
int anc = jump(S[i], L[i], 0);
// cout << anc << endl;
range1[i] = {st[anc], en[anc]};
}
for (int i = 0; i <= root; i++) {
st1[i] = st[i];
en1[i] = en[i];
}
edges.clear();
for (int i = 0; i < root; i++) g[i].clear();
for (int i = 0; i < m; i++) {
edges.emplace_back(X[i], Y[i], X[i]);
}
dsu = DSU(n);
sort(edges.begin(), edges.end());
for (int i = 0; i < m; i++) {
dsu.join(edges[i].u, edges[i].v);
}
root = dsu.n;
memset(up, -1, sizeof(up));
timedfs = 0;
dfs(root - 1, -1, 1);
// for (int i = 0; i < root; i++) {
// cout << a[i] << ' ';
// }cout << '\n';
// for (int i = 0; i < root; i++) {
// cout << i << endl;
// for (int j = 0; j < 3; j++) {
// cout << up[i][j] << ' ';
// } cout << '\n';
// }cout << '\n';
for (int i = 0; i < q; i++) {
int anc = jump(E[i], R[i], 1);
// cout << anc << endl;
range2[i] = {st[anc], en[anc]};
}
for (int i = 0; i < n; i++) {
// cout << st1[i] << ' ' << st[i] << endl;
pos[st1[i]] = st[i];
}
for (int i = 0; i < q; i++) {
event[range1[i].S].pb({i, 1});
event[range1[i].F - 1].pb({i, -1});
}
vector<int> res(q);
for (int i = 1; i <= root; i++) {
update(pos[i], 1);
for (auto it : event[i]) {
res[it.F] += (get(range2[it.F].S) - get(range2[it.F].F - 1)) * it.S;
}
}
for (int i = 0; i < q; i++) {
res[i] = (res[i] > 0);
}
return res;
}
vector<int> X, Y, S, E, L, R;
signed main(){
ios_base::sync_with_stdio(false) ;
cin.tie(0) ; cout.tie(0) ;
if (fopen("INP.INP" ,"r")) {
freopen("INP.INP" ,"r" , stdin) ;
freopen("OUT.OUT" , "w" , stdout) ;
}
cin >> n >> m >> q;
X.resize(m);
Y.resize(m);
S.resize(q);
E.resize(q);
L.resize(q);
R.resize(q);
for (int i = 0; i < m; i++) {
cin >> X[i] >> Y[i];
}
for (int i = 0; i < q; i++) {
cin >> S[i] >> E[i] >> L[i] >> R[i];
}
vector<int> res = check_validity(n, X, Y, S, E, L, R);
for (int i = 0; i < q; i++) {
cout << res[i] << '\n';
}
}