// this code is bugged
#include "werewolf.h"
#include <bits/stdc++.h>
#define sz(x) ((x).size())
#define pii pair<int, int>
#define f first
#define s second
using namespace std;
const int inf = 1e9;
const int p2 = 1<<18;
const int siz = 4e5+40;
const int LG = 20;
struct Segtree {
Segtree() {
t = new int [p2*2];
cls();
}
~Segtree() {
delete [] t;
}
void cls() {
for (int i = 0; i < p2*2; i++) t[i] = -inf;
}
void upd(int x, int v) {
for (x += p2; x; x /= 2) {
t[x] = max(t[x], v);
}
}
int get(int b, int e) {
int r = -inf;
b += p2;
e += p2;
while (b <= e) {
if (b%2 == 1) {
r = max(r, t[b]);
b++;
}
if (e%2 == 0) {
r = max(r, t[e]);
e--;
}
b /= 2;
e /= 2;
}
return r;
}
int* t;
};
vector<int> order [2];
vector<int> graph [2][siz];
vector<int> ett [2];
int posOfInEtt [2][siz];
int dsu [siz];
int jmp [2][siz][LG];
int smallerP2 [siz];
int gp(int x) {
if (dsu[x] == x) return x;
return dsu[x] = gp(dsu[x]);
}
bool merge(int x, int y) {
x = gp(x);
y = gp(y);
if (x == y) return false;
dsu[y] = x;
return true;
}
void dfs(int T, int x, int p = -1) {
ett[T].push_back(x);
for (int y : graph[T][x]) if (y != p) {
dfs(T, y, x);
// ett[T].push_back(x);
}
}
int min(int x, int y) {
return x < y ? x : y;
}
int max(int x, int y) {
return x > y ? x : y;
}
int getMinZero(int start, int end) {
int power = smallerP2[end-start+1];
return min(jmp[0][start][power], jmp[0][end-(1<<power)+1][power]);
}
int getMaxOne(int start, int end) {
int power = smallerP2[end-start+1];
return max(jmp[1][start][power], jmp[1][end-(1<<power)+1][power]);
}
std::vector<int> check_validity(const int n, std::vector<int> edgeX, std::vector<int> edgeY, std::vector<int> queryX, std::vector<int> queryY, std::vector<int> queryLB, std::vector<int> queryRB) {
for (int i = 0; i < siz; i++) {
smallerP2[i] = 0;
while ((1<<(smallerP2[i]+1)) <= i) {
smallerP2[i]++;
}
}
vector<int> adj [n];
for (int i = 0; i < sz(edgeX); i++) {
adj[edgeX[i]].push_back(edgeY[i]);
adj[edgeY[i]].push_back(edgeX[i]);
}
typedef int (*CompFunct) (int a, int b);
CompFunct funct [2] = {min, max};
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++) order[i].push_back(j);
if (i == 1) reverse(order[i].begin(), order[i].end());
for (int j = 0; j < n; j++) dsu[j] = j;
bool seen [n];
for (int j = 0; j < n; j++) seen[j] = false;
for (int jIdx = n-1; jIdx >= 0; jIdx--) {
int j = order[i][jIdx];
for (int k : adj[j]) if (seen[k]) {
int pJ = gp(j);
int pK = gp(k);
if (pJ != pK) {
graph[i][pJ].push_back(pK);
graph[i][pK].push_back(pJ);
assert(merge(pJ, pK));
}
}
seen[j] = true;
}
dfs(i, order[i][0]);
assert(sz(ett[i]) == n);
for (int j = 0; j < n; j++) {
posOfInEtt[i][ett[i][j]] = j;
}
for (int j = 0; j < n; j++) jmp[i][j][0] = ett[i][j];
for (int j = 1; j < LG; j++) {
for (int k = 0; k < n; k++) {
if (k+(1<<(j-1)) >= n) {
jmp[i][k][j] = jmp[i][k][j-1];
}
else {
jmp[i][k][j] = funct[i](jmp[i][k][j-1], jmp[i][k+(1<<(j-1))][j-1]);
}
}
}
}
const int nbQ = sz(queryX);
pii range [nbQ][2];
for (int i = 0; i < nbQ; i++) {
range[i][0] = {posOfInEtt[0][queryX[i]], posOfInEtt[0][queryX[i]]};
for (int j = p2; j; j /= 2) {
int prop = range[i][0].f-j;
if (prop < 0) continue;
if (getMinZero(prop, range[i][0].s) >= queryLB[i]) {
range[i][0].f = prop;
}
}
for (int j = p2; j; j /= 2) {
int prop = range[i][0].s+j;
if (prop >= n) continue;
if (getMinZero(range[i][0].f, prop) >= queryLB[i]) {
range[i][0].s = prop;
}
}
}
for (int i = 0; i < nbQ; i++) {
range[i][1] = {posOfInEtt[1][queryY[i]], posOfInEtt[1][queryY[i]]};
for (int j = p2; j; j /= 2) {
int prop = range[i][1].f-j;
if (prop < 0) continue;
if (getMaxOne(prop, range[i][1].s) <= queryRB[i]) {
range[i][1].f = prop;
}
}
for (int j = p2; j; j /= 2) {
int prop = range[i][1].s+j;
if (prop >= n) continue;
if (getMaxOne(range[i][1].f, prop) <= queryRB[i]) {
range[i][1].s = prop;
}
}
}
vector<int> res(nbQ, 0);
for (int i = 0; i < nbQ; i++) {
set<int> se;
for (int j = range[i][0].f; j <= range[i][0].s; j++) {
se.insert(ett[0][j]);
}
for (int j = range[i][1].f; j <= range[i][1].s; j++) {
if (se.count(ett[1][j])) {
res[i] = 1;
break;
}
}
}
return res;
}
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:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < sz(edgeX); i++) {
| ^
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from werewolf.cpp:4:
werewolf.cpp:137:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
137 | assert(sz(ett[i]) == n);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
20692 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
20616 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
20692 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
20616 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4077 ms |
103708 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
20692 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
20616 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
