#include "werewolf.h"
#include <iostream>
#include <vector>
#define f first
#define s second
using namespace std;
int n, m, q, p[200010], id[200010], pmax[600010][21], pmin[600010][21], vmax[600010], vmin[600010], mxsz, mnsz, cnt;
pair<int,int> rmax[600010], rmin[600010];
vector<int> edge[200010], maxx[600010], minn[600010], node[800010];
int dsu(int u) {
if (p[u] == u) return u;
return (p[u] = dsu(p[u]));
}
void buildmax(int u) {
int v = pmax[u][0];
for (int i = 1; i <= 20; i++) {
if (v == -1) break;
pmax[u][i] = pmax[v][i-1];
v = pmax[u][i];
}
if (maxx[u].empty()) {
++cnt;
rmax[u] = {cnt,cnt};
return;
}
for (int i = 0; i < maxx[u].size(); i++) {
buildmax(maxx[u][i]);
rmax[u] = {min(rmax[u].f,rmax[maxx[u][i]].f),max(rmax[u].s,rmax[maxx[u][i]].s)};
}
}
void buildmin(int u) {
int v = pmin[u][0];
for (int i = 1; i <= 20; i++) {
if (v == -1) break;
pmin[u][i] = pmin[v][i-1];
v = pmin[u][i];
}
if (minn[u].empty()) {
node[1].push_back(rmax[u].f);
rmin[u] = {cnt,cnt};
cnt++;
return;
}
for (int i = 0; i < minn[u].size(); i++) {
buildmin(minn[u][i]);
rmin[u] = {min(rmin[u].f,rmin[minn[u][i]].f),max(rmin[u].s,rmin[minn[u][i]].s)};
}
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
vector<int> ans;
n = N; m = X.size(); q = S.size();
for (int i = 0; i < m; i++) {
edge[X[i]].push_back(Y[i]);
edge[Y[i]].push_back(X[i]);
}
for (int i = 0; i < n+m; i++) for (int j = 0; j <= 20; j++) pmax[i][j] = pmin[i][j] = -1;
for (int i = 0; i < n; i++) p[i] = id[i] = vmin[i] = i;
mnsz = n-1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < edge[i].size(); j++) {
if (edge[i][j] < i) {
int u = edge[i][j], v = i;
if (p[dsu(u)] != p[dsu(v)]) {
++mnsz;
pmin[id[p[dsu(u)]]][0] = pmin[id[p[dsu(v)]]][0] = mnsz;
minn[mnsz].push_back(id[p[dsu(u)]]);
minn[mnsz].push_back(id[p[dsu(v)]]);
p[dsu(v)] = p[dsu(u)];
id[p[dsu(u)]] = mnsz;
vmin[mnsz] = i;
}
}
}
}
mxsz = n-1;
for (int i = 0; i < n; i++) p[i] = id[i] = vmax[i] = i;
for (int i = n-1; i >= 0; i--) {
for (int j = 0; j < edge[i].size(); j++) {
if (edge[i][j] > i) {
int u = edge[i][j], v = i;
if (p[dsu(u)] != p[dsu(v)]) {
++mxsz;
pmax[id[p[dsu(u)]]][0] = pmax[id[p[dsu(v)]]][0] = mxsz;
maxx[mxsz].push_back(id[p[dsu(u)]]);
maxx[mxsz].push_back(id[p[dsu(v)]]);
p[dsu(v)] = p[dsu(u)];
id[p[dsu(u)]] = mxsz;
vmax[mxsz] = i;
}
}
}
}
for (int i = 0; i <= mxsz; i++) rmax[i] = {1e9,-1e9};
for (int i = 0; i <= mnsz; i++) rmin[i] = {1e9,-1e9};
buildmax(mxsz);
cnt = 0;
buildmin(mnsz);
for (int _ = 0; _ < q; _++) {
int u = S[_], v = E[_], l = L[_], r = R[_];
for (int j = 20; j >= 0; j--) if (vmax[pmax[u][j]] >= l) u = pmax[u][j];
for (int j = 20; j >= 0; j--) if ((pmin[v][j] != -1) && (vmin[pmin[v][j]] <= r)) v = pmin[v][j];
for (int i = rmin[v].f; i <= rmin[v].s; i++) {
if ((rmax[u].f <= node[1][i]) && (node[1][i] <= rmax[u].s)) {
ans.push_back(1);
goto skip;
}
}
ans.push_back(0);
skip:;
}
return ans;
}
Compilation message
werewolf.cpp: In function 'void buildmax(int)':
werewolf.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i = 0; i < maxx[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void buildmin(int)':
werewolf.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i = 0; i < minn[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int j = 0; j < edge[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~
werewolf.cpp:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int j = 0; j < edge[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
51972 KB |
Output is correct |
| 2 |
Incorrect |
28 ms |
51980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
51972 KB |
Output is correct |
| 2 |
Incorrect |
28 ms |
51980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
648 ms |
160908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
51972 KB |
Output is correct |
| 2 |
Incorrect |
28 ms |
51980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
