#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int lg = 19;
int n;
vector<vector<int>> A;
vector<array<int, 2>> P, L, R, Vis, Dsc, Fin;
vector<vector<array<int, 2>>> Up;
int find(int ind, int id) {
if (P[ind][id] == ind) {
return ind;
}
return P[ind][id] = find(P[ind][id], id);
}
array<int, 2> cnt;
void merge(int a, int b, int id) {
int ga = find(a, id), gb = find(b, id);
if (ga == gb) {
return ;
}
L[cnt[id]][id] = ga, R[cnt[id]][id] = gb;
Up[ga][0][id] = Up[gb][0][id] = P[ga][id] = P[gb][id] = cnt[id]++;
return;
}
array<int, 2> time_;
void build(int u, int id) {
Dsc[u][id] = time_[id]++;
Vis[u][id] = 1;
if (Up[u][0][id] == -1) {
for (int j = 0; j <= lg; j++) {
Up[u][j][id] = u;
}
}
else {
for (int j = 1; j <= lg; j++) {
Up[u][j][id] = Up[Up[u][j - 1][id]][j - 1][id];
}
}
if (u >= n) {
build(L[u][id], id);
build(R[u][id], id);
}
Fin[u][id] = time_[id]++;
}
int lca(int u, int c, int id) {
for (int j = lg; j >= 0; j--) {
if (Up[u][j][id] <= c) {
u = Up[u][j][id];
}
}
return u;
}
vector<int> check_validity(int nn, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> LL, vector<int> RR) {
n = nn;
cnt[0] = cnt[1] = n;
A.resize(n), P.resize(2 * n), L.resize(2 * n), R.resize(2 * n), Vis.resize(2 * n), Dsc.resize(2 * n), Fin.resize(2 * n);
Up.resize(2 * n, vector<array<int, 2>>(lg + 1, {-1, -1}));
for (int i = 0; i < 2 * n; i++) {
P[i][0] = P[i][1] = i;
}
for (int i = 0; i < X.size(); i++) {
A[X[i]].push_back(Y[i]);
A[Y[i]].push_back(X[i]);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < A[i].size(); j++) {
if (A[i][j] < i) {
merge(i, A[i][j], 0);
}
}
}
vector<int> Ans(LL.size());
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < A[i].size(); j++) {
if (A[i][j] > i) {
merge(i, A[i][j], 1);
}
}
}
for (int j = 0; j < 2; j++) {
for (int i = cnt[j] - 1; i >= 0; i--) {
if (!Vis[i][j]) {
build(i, j);
}
}
}
for (int i = 0; i < S.size(); i++) {
int u = lca(S[i], RR[i] + n - 1, 0), v = lca(E[i], (n - 1) - LL[i] + n - 1, 1);
for (int j = 0; j < n; j++) {
if (Dsc[j][0] >= Dsc[u][0] && Dsc[j][0] <= Fin[u][0]) {
if (Dsc[j][1] >= Dsc[v][1] && Dsc[j][1] <= Fin[v][1]) {
Ans[i] = 1;
}
}
}
}
return Ans;
}
Compilation message
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:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int i = 0; i < X.size(); i++) {
| ~~^~~~~~~~~~
werewolf.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int j = 0; j < A[i].size(); j++) {
| ~~^~~~~~~~~~~~~
werewolf.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int j = 0; j < A[i].size(); j++) {
| ~~^~~~~~~~~~~~~
werewolf.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for (int i = 0; i < S.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4050 ms |
126804 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
