#include <bits/stdc++.h>
#include "werewolf.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
struct Seg {
int n;
vii seg;
Seg (int m) {
for (n = 1; n < m; n <<= 1);
seg.resize(2 * n, {0, n});
}
void update(int i, int x) {
for (i += n; i; i >>= 1) {
chkmax(seg[i].x, x);
chkmin(seg[i].y, x);
}
}
pii query(int l, int r) {
pii ans = {0, n};
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
chkmax(ans.x, seg[l].x);
chkmin(ans.y, seg[l].y);
l++;
}
if (r & 1) {
--r;
chkmax(ans.x, seg[r].x);
chkmin(ans.y, seg[r].y);
}
}
return ans;
}
};
void DfsMax(vvi &graph, int node, int max, vb &visited) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (neighbor <= max && !visited[neighbor]) DfsMax(graph, neighbor, max, visited);
}
}
void DfsMin(vvi &graph, int node, int min, vb &visited) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (neighbor >= min && !visited[neighbor]) DfsMin(graph, neighbor, min, visited);
}
}
const int MAX_N = 2e5 + 5;
int par[MAX_N], sz[MAX_N];
void init(int n) {
iota(par, par + n, 0);
fill(sz, sz + n, 1);
}
int Find(int i) {
return par[i] == i ? i : par[i] = Find(par[i]);
}
bool Union(int a, int b) {
int pa = Find(a), pb = Find(b);
if (pa == pb) return false;
if (sz[pa] < sz[pb]) swap(pa, pb);
sz[pa] += sz[pb];
par[pb] = pa;
return true;
}
int ind[MAX_N];
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
int m = x.size();
iota(ind, ind + m, 0);
sort(ind, ind + m, [&] (int i, int j) {
return max(x[i], y[i]) < max(x[j], y[j]);
});
init(n);
vvi graph(n);
for (int i = 0; i < m; i++) {
if (Union(x[ind[i]], y[ind[i]])) {
graph[x[ind[i]]].push_back(y[ind[i]]);
graph[y[ind[i]]].push_back(x[ind[i]]);
}
}
// for (int i = 0; i < m; i++) {
// graph[x[i]].push_back(y[i]);
// graph[y[i]].push_back(x[i]);
// }
// int start = 0;
// for (; start < n; start++) {
// if (graph[start].size() == 1) break;
// }
// bitset<MAX_N> visited;
// for (int i = 0; i < n; i++) {
// ind[start] = i;
// visited[start] = true;
// for (int neighbor : graph[start]) {
// if (!visited[neighbor]) {
// start = neighbor;
// break;
// }
// }
// }
// Seg seg(n);
// for (int i = 0; i < n; i++) {
// seg.update(ind[i], i);
// }
int q = s.size();
vi ans(q);
for (int i = 0; i < q; i++) {
// int v = ind[s[i]], u = ind[e[i]];
// if (v < u) {
// int begin = v, end = u + 1, mid;
// while (begin < end) {
// mid = (begin + end) >> 1;
// if (seg.query(v, mid + 1).y < l[i]) end = mid;
// else begin = mid + 1;
// }
// int right = end - 1;
// begin = v, end = u;
// while (begin < end) {
// mid = (begin + end) >> 1;
// if (seg.query(mid, u).x > r[i]) begin = mid + 1;
// else end = mid;
// }
// int left = end;
// ans[i] = right >= left;
// } else {
// swap(v, u);
// int begin = v, end = u + 1, mid;
// while (begin < end) {
// mid = (begin + end) >> 1;
// if (seg.query(v, mid + 1).x > r[i]) end = mid;
// else begin = mid + 1;
// }
// int right = end - 1;
// begin = v, end = u;
// while (begin < end) {
// mid = (begin + end) >> 1;
// if (seg.query(mid, u).y < l[i]) begin = mid + 1;
// else end = mid;
// }
// int left = end;
// ans[i] = right >= left;
// }
vb visited1(n), visited2(n);
DfsMin(graph, s[i], l[i], visited1);
DfsMax(graph, e[i], r[i], visited2);
for (int j = 0; j < n; j++) {
if (visited1[j] && visited2[j]) {
ans[i] = 1;
break;
}
}
}
return ans;
}
//6 6 3
//0 3
//1 2
//1 5
//1 3
//2 5
//3 4
//
//4 2 1 2
//4 2 2 2
//5 4 3 4
//6 5 3
//1 3
//3 0
//0 4
//4 5
//5 2
//
//3 5 0 5
//2 1 0 4
//4 2 3 4
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4062 ms |
42720 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
