#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;
}
return false;
}
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;
int s = S[i], e = E[i];
for(int j = LOGN - 1; j >= 0; j--){
if(upV[s][j] >= L[i]){
s = upV[s][j];
}
if(upU[e][j] <= R[i]){
e = upU[e][j];
}
}
l2 = tinV[s];
r2 = toutV[s];
l1 = tinU[e];
r1 = toutU[e];
//cout << s << " S[I] E[i] " << e << endl;
//cout << l2 << " " << r2 << " - " << l1 << " " << r1 << endl;
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 i = 0; i < ans.size(); i++){
int &x = ans[i];
if(S[i] < L[i] || E[i] > R[i]){
x = 0;
continue;
}
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:135:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < X.size(); i++){
~~^~~~~~~~~~
werewolf.cpp:240:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ans.size(); i++){
~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
17664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
17664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
951 ms |
104892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
17664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
