#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define vi vector<int>
#define pii pair<int, int>
const int MX = 1e6 + 5;
vector<int> gr[4][MX];
int vis[MX];
int n, m, q;
vi X, Y, S, E, L, R;
struct KRT{
int n;
vector<int> p;
KRT(int N){
this->n = N;
p.assign(2 * N + 5, 0);
for(int i=1; i<=n; ++i){
p[i] = i;
}
}
int get(int u){
return (u == p[u] ? u : p[u] = get(p[u]));
}
void add(int u, int v, int k){
u = get(u), v = get(v);
if(u == v){
return;
}
p[v] = u;
gr[k][u].push_back(v);
}
};
struct BIT{
int n;
vector<int> f;
BIT(int N){
this->n = N + 5;
f.assign(N + 5, 0);
}
void update(int i, int val){
while(i < n){
f[i] += val;
i += (i & -i);
}
}
int get(int i){
int ans = 0;
while(i > 0){
ans += f[i];
i -= (i & -i);
}
return ans;
}
int get(int l, int r){
return get(r) - get(l - 1);
}
};
struct query{
int l, r, e, s, idx;
};
int in[4][MX], ou[4][MX];
int eu[4][MX];
int id = 0;
void dfs(int u, int p, int k){
eu[k][++id] = u;
in[k][u] = id;
for(int v : gr[k][u]){
if(v != p){
dfs(v, u, k);
eu[k][++id] = u;
ou[k][u] = id;
}
}
}
vector<int> check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R){ //returns boolean vector.
for(int i=0; i<m; ++i){
int u = X[i], v = Y[i];
gr[1][u].push_back(v);
gr[1][v].push_back(u);
}
KRT up(n), dn(n);
for(int i=1; i<=n; ++i){
for(int u : gr[1][i]){
if(vis[u] == 1){
up.add(i, u, 2);
}
}
vis[i] = 1;
}
for(int i=n; i>=1; --i){
for(int u : gr[1][i]){
if(vis[u] == 2){
dn.add(i, u, 3);
}
}
vis[i] = 2;
}
for(int i=1; i<=n; ++i){
if(up.get(i) == i){
dfs(i, 0, 2);
break;
}
}
id = 0;
for(int i=1; i<=n; ++i){
if(dn.get(i) == i){
dfs(i, 0, 3);
break;
}
}
vector<query> Q;
vector<int> ans;
for(int i=0; i<q; ++i){
int s = S[i], e = E[i], l = L[i], r = R[i];
set<int> se;
for(int j=in[3][l]+1; j<ou[3][l]; ++j){
se.insert(eu[3][j]);
}
int f = 0;
for(int j=in[2][r]+1; j<ou[2][r]; ++j){
if(se.find(eu[2][j]) != se.end()){
f = 1;
}
}
ans.push_back(f);
}
return ans;
}
// int32_t main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// freopen("main.inp","r",stdin);
// freopen("main.out","w",stdout);
// cin>>n>>m>>q;
// for(int i=1; i<=m; ++i){
// int u, v;
// cin>>u>>v;
// ++u, ++v;
// X.push_back(u);
// Y.push_back(v);
// }
// for(int i=1; i<=q; ++i){
// int s, e, l, r;
// cin>>s>>e>>l>>r;
// ++s, ++e, ++l, ++r;
// S.push_back(s), E.push_back(e), L.push_back(l), R.push_back(r);
// }
// vector<int> ans = check_validity(n, X, Y, S, E, L, R);
// for(int x : ans){
// cout<<x<<' ';
// }
// return 0;
// }
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:128:13: warning: unused variable 's' [-Wunused-variable]
128 | int s = S[i], e = E[i], l = L[i], r = R[i];
| ^
werewolf.cpp:128:23: warning: unused variable 'e' [-Wunused-variable]
128 | int s = S[i], e = E[i], l = L[i], r = R[i];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
106076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
106076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
120656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
106076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
