#include <bits/stdc++.h>
//#include "werewolf.h"
using namespace std;
const int INF = 1e9;
struct SegTree {
struct Node {
int ma, mi;
Node(int m1, int m2) : ma(m1),mi(m2) {}
Node(int v) : ma(v), mi(v) {}
Node() : ma(-INF),mi(INF) {}
};
vector<Node> seg;
int MAX;
SegTree(int N) {
int i;
for(i=2;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
}
Node f(Node x, Node y) {
return Node(max(x.ma,y.ma),min(x.mi,y.mi));
}
void cons() {
for(int i = MAX/2-1;i>0;i--) {
seg[i] = f(seg[2*i],seg[2*i+1]);
}
}
Node sum(int s, int e, int n, int ns, int ne) {
if(e<=ns||ne<=s) return Node();
if(s<=ns&&ne<=e) return seg[n];
int mid = ns + ne >> 1;
return f(sum(s,e,2*n,ns,mid),sum(s,e,2*n+1,mid,ne));
}
Node sum(int s, int e) {
return sum(s, e, 1, 0, MAX/2);
}
int LeftSmall(int s, int e, int k) {
if(e == s + 1) {
if(seg[s+MAX/2].ma <= k) return s;
else return INF;
}
int mid = s + e >> 1;
if(sum(s,mid).mi <= k) return LeftSmall(s,mid,k);
return LeftSmall(mid,e,k);
}
int RightSmall(int s, int e, int k) {
if(e == s + 1) {
if(seg[s+MAX/2].ma <= k) return s;
else return -INF;
}
int mid = s + e >> 1;
if(sum(mid,e).mi <= k) return RightSmall(mid,e,k);
return RightSmall(s,mid,k);
}
int LeftBig(int s, int e, int k) {
if(e == s + 1) {
if(seg[s+MAX/2].ma >= k) return s;
else return INF;
}
int mid = s + e >> 1;
if(sum(s,mid).ma >= k) return LeftBig(s,mid,k);
return LeftBig(mid,e,k);
}
int RightBig(int s, int e, int k) {
if(e == s + 1) {
if(seg[s+MAX/2].ma >= k) return s;
else return -INF;
}
int mid = s + e >> 1;
if(sum(mid,e).ma >= k) return RightBig(mid,e,k);
return RightBig(s,mid,k);
}
};
typedef pair<int,int> P;
vector<vector<int> > adj;
vector<vector<P> > QueryL;
vector<vector<P> > QueryR;
int A[200005];
int B[200005];
struct UnionFind {
vector<int> root;
UnionFind(int N) {
root.resize(N);
fill(root.begin(),root.end(),-1);
}
int Find(int n) {
if(root[n] < 0) return n;
int r = Find(root[n]);
root[n] = r;
return r;
}
void Merge(int x, int y) {
x = Find(x);
y = Find(y);
if(x == y) return;
if(root[x] > root[y]) swap(x, y);
root[x] += root[y];
root[y] = x;
}
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
vector<int> ans;
int Q = S.size();
int M = X.size();
if(N <= 3000 && M <= 6000 && Q <= 3000) {
vector<vector<bool> > isCan1, isCan2;
isCan1.resize(Q);
isCan2.resize(Q);
int i;
for(i=0;i<Q;i++) {
isCan1[i].resize(N);
isCan2[i].resize(N);
}
adj.resize(N);
for(i=0;i<M;i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(i=0;i<Q;i++) {
QueryL[L[i]].push_back(P(S[i],i));
QueryR[R[i]].push_back(P(E[i],i));
}
UnionFind UF1(N);
for(i=N-1;i>=0;i--) {
for(int n : adj[i]) {
if(n > i) UF1.Merge(n, i);
}
for(P k : QueryL[i]) {
for(int j = 0; j < N; j++) {
if(UF1.Find(j)==UF1.Find(k.first)) {
isCan1[k.second][j] = true;
}
}
}
}
UnionFind UF2(N);
for(i = 0; i < N;i++) {
for(int n : adj[i]) {
if(n < i) UF2.Merge(n, i);
}
for(P k : QueryR[i]) {
for(int j = 0; j <N; j++) {
if(UF2.Find(j) == UF2.Find(k.first)) {
isCan2[k.second][j] = true;
}
}
}
}
ans.resize(Q);
for(i=0;i<Q;i++) {
for(int j = 0; j < N;j++){
if(isCan1[i][j] && isCan2[i][j]) ans[i] = 1;
}
}
return ans;
}
adj.resize(N);
int i;
for(i=0;i<M;i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
int st;
for(i=0;i<M;i++) {
if(adj[i].size()==1) st = i;
}
int p = -1, c = st;
i = 0;
while(i != N) {
A[i] = c;
B[c] = i;
for(int n : adj[c]) {
if(n != p) {
p = c;
c = n;
break;
}
}
i++;
}
//for(i=0;i<N;i++) cout << A[i] << ' ';
//cout << '\n';
SegTree tree(N+5);
int MAX = tree.MAX;
for(i=0;i<N;i++) {
tree.seg[i+MAX/2].ma = A[i];
tree.seg[i+MAX/2].mi = A[i];
}
tree.cons();
for(i=0;i<Q;i++) {
int x = B[S[i]];
int y = B[E[i]];
int l = L[i];
int r = R[i];
if(S[i] < L[i] || R[i] < E[i]) {
ans.push_back(0);
continue;
}
if(x < y) {
int k1 = tree.LeftSmall(x, y+1, l-1) - 1;
int k2 = tree.RightBig(x, y+1, r+1)+1;
//cout << x << ' ' << y << ' ' << k1 << ' ' << k2 << '\n';
if(k1 >= k2) ans.push_back(1);
else ans.push_back(0);
}
else {
int k1 = tree.LeftBig(y, x+1, r+1)-1;
int k2 = tree.RightSmall(y, x + 1, l-1) + 1;
//cout << x << ' ' << y << ' ' << k1 << ' ' << k2 << '\n';
if(k1 >= k2) ans.push_back(1);
else ans.push_back(0);
}
}
return ans;
}
Compilation message
werewolf.cpp: In member function 'SegTree::Node SegTree::sum(int, int, int, int, int)':
werewolf.cpp:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
31 | int mid = ns + ne >> 1;
| ~~~^~~~
werewolf.cpp: In member function 'int SegTree::LeftSmall(int, int, int)':
werewolf.cpp:42:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | int mid = s + e >> 1;
| ~~^~~
werewolf.cpp: In member function 'int SegTree::RightSmall(int, int, int)':
werewolf.cpp:51:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int mid = s + e >> 1;
| ~~^~~
werewolf.cpp: In member function 'int SegTree::LeftBig(int, int, int)':
werewolf.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int mid = s + e >> 1;
| ~~^~~
werewolf.cpp: In member function 'int SegTree::RightBig(int, int, int)':
werewolf.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int mid = s + e >> 1;
| ~~^~~
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:174:26: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
174 | for(int n : adj[c]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1916 ms |
28440 KB |
Output is correct |
| 2 |
Correct |
2044 ms |
28916 KB |
Output is correct |
| 3 |
Correct |
2171 ms |
28544 KB |
Output is correct |
| 4 |
Correct |
2131 ms |
28616 KB |
Output is correct |
| 5 |
Correct |
2037 ms |
28752 KB |
Output is correct |
| 6 |
Correct |
1884 ms |
28900 KB |
Output is correct |
| 7 |
Correct |
1925 ms |
28740 KB |
Output is correct |
| 8 |
Correct |
1941 ms |
28732 KB |
Output is correct |
| 9 |
Correct |
875 ms |
28604 KB |
Output is correct |
| 10 |
Correct |
990 ms |
28556 KB |
Output is correct |
| 11 |
Correct |
1157 ms |
28692 KB |
Output is correct |
| 12 |
Correct |
1437 ms |
28788 KB |
Output is correct |
| 13 |
Correct |
2082 ms |
28592 KB |
Output is correct |
| 14 |
Correct |
1878 ms |
28676 KB |
Output is correct |
| 15 |
Correct |
1977 ms |
28808 KB |
Output is correct |
| 16 |
Correct |
1913 ms |
28612 KB |
Output is correct |
| 17 |
Correct |
1979 ms |
28876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
