#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T, typename U>
void miner(T &MIN, U CMP) { if(MIN > CMP) MIN = CMP; }
template<typename T, typename U>
void maxer(T &MAX, U CMP) { if(MAX < CMP) MAX = CMP; }
#define ff first
#define ss second
#define MP make_pair
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
const int inf = 1e9 + 10;
const int mxn = 2e5 + 10;
const int MXN = 4e5 + 10;
int LQ[mxn], RQ[mxn];
int mx[MXN], mn[MXN];
int n, m, q;
int parent(int u, vi &par) {
if(par[u] < 0) return u;
return par[u] = parent(par[u], par);
}
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<pair<pii, int>> LE, RE;
for(int i = 0; i < m; i++) {
int u = X[i];
int v = Y[i];
if(u > v) swap(u, v);
LE.push_back(MP(MP(u, inf), v));
RE.push_back(MP(MP(v, -inf), u));
}
for(int i = 0; i < q; i++) {
int l = L[i], r = R[i];
int s = S[i], e = E[i];
LE.push_back(MP(MP(l, i), s));
RE.push_back(MP(MP(r, i), e));
}
sort(LE.begin(), LE.end(), [&](auto L, auto R) { return L > R; });
sort(RE.begin(), RE.end());
int cur = n;
vi L_anc(2 * n, -1);
for(int i = 0; i < n; i++)
mn[i] = i;
for(auto e : LE) {
int id = e.ff.ss;
int u = parent(e.ff.ff, L_anc);
int v = parent(e.ss, L_anc);
if(id != inf) {
LQ[id] = mn[v];
continue;
}
if(u == v) continue;
L_anc[u] = cur;
L_anc[v] = cur;
mn[cur] = e.ff.ff;
miner(mn[cur], mn[u]);
miner(mn[cur], mn[v]);
// cout << e.ff.ff << ' ' << e.ss << " -> "
// << u << ' ' << v << " = "
// << cur << ": " << mn[cur] << endl;
cur++;
}
mn[cur] = -inf;
assert(cur == 2 * n - 1);
// cout << "----------------\n";
cur = n;
vi R_anc(2 * n, -1);
for(int i = 0; i < n; i++)
mx[i] = i;
for(auto e : RE) {
int id = e.ff.ss;
int u = parent(e.ff.ff, R_anc);
int v = parent(e.ss, R_anc);
if(id != -inf) {
RQ[id] = mx[v];
continue;
}
if(u == v) continue;
R_anc[u] = cur;
R_anc[v] = cur;
mx[cur] = e.ff.ff;
maxer(mx[cur], mx[u]);
maxer(mx[cur], mx[v]);
// cout << e.ff.ff << ' ' << e.ss << " -> "
// << u << ' ' << v << " = "
// << cur << ": " << mx[cur] << endl;
cur++;
}
mx[cur] = inf;
assert(cur == 2 * n - 1);
vi par(n, -1);
for(int i = 0; i < m; i++) {
int u = parent(X[i], par);
int v = parent(Y[i], par);
if(u == v) continue;
par[u] += par[v];
par[v] = u;
}
vector<int> ans;
for(int i = 0; i < q; i++) {
int l = L[i], r = R[i];
if(RQ[i] < l || r < LQ[i]) {
ans.push_back(0);
continue;
}
int SL = parent(LQ[i], par);
int SR = parent(RQ[i], par);
if(SL == SR)
ans.push_back(1);
else
ans.push_back(0);
}
return ans;
}
/*
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4432 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4432 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
224 ms |
40964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4432 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
