#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
const int LOGN = 20;
struct dsu{
int par[MAXN], cnt[MAXN];
dsu(){
for(int i = 0; i < MAXN; i++){
par[i] = i;
cnt[i] = 1;
}
}
void find_par(int u){
if(u == par[u]){
return;
}
find_par(par[u]);
par[u] = par[par[u]];
}
};
dsu du, dv;
vector<int> adj[MAXN], ans;
vector<int> U[MAXN], V[MAXN];
int tinU[MAXN], tinV[MAXN];
int toutU[MAXN], toutV[MAXN];
vector<int> eU, eV, inv;
int upU[MAXN][LOGN], upV[MAXN][LOGN];
void dfsU(int u, int p){
eU.push_back(u);
tinU[u] = (int)eU.size() - 1;
upU[u][0] = p;
for(int to: U[u]){
if(to == p){
continue;
}
dfsU(to, u);
//eU.push_back(u);
}
toutU[u] = (int)eU.size() - 1;
}
void dfsV(int u, int p){
eV.push_back(u);
tinV[u] = (int)eV.size() - 1;
upV[u][0] = p;
for(int to: V[u]){
if(to == p){
continue;
}
dfsV(to, u);
//eV.push_back(u);
}
toutV[u] = (int)eV.size() - 1;
}
int fenwick[MAXN];
void update_fenwick(int idx, int delta){
idx++;
for(; idx < MAXN; idx += (idx & -idx)){
fenwick[idx] += delta;
}
}
int query_fenwick(int idx){
int ret = 0;
idx++;
for(; idx >= 1; idx -= (idx & -idx)){
ret += fenwick[idx];
}
return ret;
}
int range_fenwick(int l, int r){
if(l == 0){
return query_fenwick(r);
}
return query_fenwick(r) - query_fenwick(l - 1);
}
struct query{
short type;
int x, y1, y2, idx;
query(){}
query(int x, int y){
type = 2;
this->x = x;
y1 = y;
y2 = -1;
idx = -1;
}
query(int x, int y1, int y2, short type, int idx){
this->type = type;
this->x = x;
this->y1 = y1;
this->y2 = y2;
this->idx = idx;
}
};
bool cmp(query lvalue, query rvalue){
if(lvalue.x != rvalue.x){
return lvalue.x < rvalue.x;
}
}
vector<query> q;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
for(int i = 0; i < X.size(); i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i = 0; i < N; i++){
for(int to: adj[i]){
if(to < i){
du.find_par(i);
du.find_par(to);
if(du.par[i] == du.par[to]){
continue;
}
U[ du.par[i] ].push_back(du.par[to]);
U[ du.par[to] ].push_back(du.par[i]);
du.par[du.par[to]] = du.par[i];
}
}
}
dfsU(N - 1, N - 1);
for(int i = N - 1; i >= 0; i--){
for(int to: adj[i]){
if(to > i){
dv.find_par(i);
dv.find_par(to);
if(dv.par[i] == dv.par[to]){
continue;
}
V[ dv.par[i] ].push_back(dv.par[to]);
V[ dv.par[to] ].push_back(dv.par[i]);
dv.par[dv.par[to]] = dv.par[i];
}
}
}
dfsV(0, 0);
for(int j = 1; j < LOGN; j++){
for(int i = 0; i < N; i++){
upU[i][j] = upU[upU[i][j - 1]][j - 1];
upV[i][j] = upV[upV[i][j - 1]][j - 1];
}
}
for(int i = 0; i < N; i++){
inv.push_back(0);
}
for(int i = 0; i < N; i++){
inv[eV[i]] = i;
}
for(int i = 0; i < N; i++){
q.push_back(query(eU[i], inv[i]));
}
for(int i = 0; i < (int)S.size(); i++){
int l1, r1, l2, r2;
l2 = tinV[S[i]];
r2 = toutV[S[i]];
l1 = tinU[E[i]];
r1 = toutU[E[i]];
q.push_back(query(l1 - 1, l2, r2, 0, i));
q.push_back(query(r1, l2, r2, 1, i));
ans.push_back(0);
}
sort(q.begin(), q.end(), cmp);
for(query t: q){
if(t.type == 0){
ans[t.idx] -= range_fenwick(t.y1, t.y2);
continue;
}
if(t.type == 1){
ans[t.idx] += range_fenwick(t.y1, t.y2);
continue;
}
if(t.type == 2){
update_fenwick(t.x, 1);
continue;
}
}
for(int &x: ans){
if(x > 0){
x = 1;
}
else{
x = 0;
}
}
return ans;
}
/*vector<int> xv, yv, sv, ev, lv, rv, res;
int main(){
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int x, y;
cin >> x >> y;
xv.push_back(x);
yv.push_back(y);
}
int q;
cin >> q;
for(int i = 0; i < q; i++){
int sx, ex, lx, rx;
cin >> sx >> ex >> lx >> rx;
sv.push_back(sx);
ev.push_back(ex);
lv.push_back(lx);
rv.push_back(rx);
}
res = check_validity(n, xv, yv, sv, ev, lv, rv);
for(int t: res){
if(t > 0){
cout << "1 ";
}
else{
cout << "0 ";
}
}
cout << endl;
return 0;
}*/
/*
3 3
0 1
0 2
2 1
2
0 1 1 1
1 0 1 2
*/
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:132:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < X.size(); i++){
~~^~~~~~~~~~
werewolf.cpp: In function 'bool cmp(query, query)':
werewolf.cpp:127:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
35200 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
35200 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
793 ms |
200432 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
35200 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
