#include "werewolf.h"
#include <vector>
#include <algorithm>
#include <deque>
#include <iostream>
using namespace std;
#define MAX_N 200000
vector<int> gp[MAX_N+1];
vector<int> ans;
struct ST{
int s, e;
int l, r;
vector<int> v;
};
vector<ST> MST;
vector<int> ex;
int Lp[MAX_N+1][20], Rp[MAX_N+1][20];
int Lg[MAX_N+1], Rg[MAX_N+1];
int fLg(int x){
if(x==Lg[x]) return x;
return Lg[x]=fLg(Lg[x]);
}
int fRg(int x){
if(x==Rg[x]) return x;
return Rg[x]=fRg(Rg[x]);
}
int n, m, q;
vector<int> lgp[MAX_N+1], rgp[MAX_N+1];
int lidx[MAX_N+1][2], ridx[MAX_N+1][2];
int idx=0;
void ldfs(int x){
lidx[x][0]=++idx;
for(int i=0; i<lgp[x].size(); i++){
ldfs(lgp[x][i]);
}
lidx[x][1]=idx;
}
void rdfs(int x){
ridx[x][0]=++idx;
for(int i=0; i<rgp[x].size(); i++){
rdfs(rgp[x][i]);
}
ridx[x][1]=idx;
}
int arr[MAX_N+1];
deque<int> dq;
void init(){
int x=0;
dq.push_back(0);
while(!dq.empty()){
x=dq.front(); dq.pop_front();
if(MST[x].s!=MST[x].e){
if(MST[x].l==-1){
MST[x].l=(int)MST.size();
MST.push_back({MST[x].s, (MST[x].s+MST[x].e)/2, -1, -1, ex});
dq.push_back(MST[x].l);
}
if(MST[x].r==-1){
MST[x].r=(int)MST.size();
MST.push_back({(MST[x].s+MST[x].e)/2+1, MST[x].e, -1, -1, ex});
dq.push_back(MST[x].r);
}
}else {MST[x].v.push_back(arr[MST[x].s]);}
}
dq.clear();
int i1=0, i2=0;
x=(int)MST.size()-1;
while(1){
if(MST[x].s!=MST[x].e){
i1=i2=0;
//MST[x].v.resize(MST[MST[x].l].v.size()+MST[MST[x].r].v.size());
while(1){
if(i1==MST[MST[x].l].v.size() && i2==MST[MST[x].r].v.size()) break;
if(i1==MST[MST[x].l].v.size()){
MST[x].v.push_back(MST[MST[x].r].v[i2++]);
}else if(i2==MST[MST[x].r].v.size()){
MST[x].v.push_back(MST[MST[x].l].v[i1++]);
}else{
if(MST[MST[x].l].v[i1]<MST[MST[x].r].v[i2]){
MST[x].v.push_back(MST[MST[x].l].v[i1++]);
}else{
MST[x].v.push_back(MST[MST[x].r].v[i2++]);
}
}
}
}
if(x==0) return;
x--;
}
}
ST now;
vector<int>::iterator it;
bool check(int idx, int x, int y, int z, int w){
if(MST[idx].s>y || now.e<x) return false;
if(MST[idx].s==MST[idx].e) return (z<=MST[idx].v.back() && MST[idx].v.back()<=w);
if(x<=MST[idx].s && MST[idx].e<=y){
it=lower_bound(MST[idx].v.begin(), MST[idx].v.end(), z);
if(it==MST[idx].v.end()) return false;
return (*it<=w);
}
if(check(MST[idx].l, x, y, z, w)) return true;
return check(MST[idx].r, x, y, z, w);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
n=N; m=(int)X.size(); q=(int)S.size();
for(int i=0; i<m; i++){
gp[X[i]].push_back(Y[i]); gp[Y[i]].push_back(X[i]);
}
for(int i=0; i<n; i++){
Lg[i]=Rg[i]=i;
Lp[i][0]=0; Rp[i][0]=n-1;
}
for(int i=n-1; i>=0; i--){
for(int j=0; j<gp[i].size(); j++){
if(gp[i][j]>i){
int a=fLg(i), b=fLg(gp[i][j]);
if(a!=b){
Lg[b]=a; Lp[b][0]=a; lgp[a].push_back(b);
}
}
}
}
idx=-1; ldfs(fLg(0));
for(int i=0; i<n; i++){
for(int j=0; j<gp[i].size(); j++){
if(gp[i][j]<i){
int a=fRg(i), b=fRg(gp[i][j]);
if(a!=b){
Rg[b]=a; Rp[b][0]=a; rgp[a].push_back(b);
}
}
}
}
idx=-1; rdfs(fRg(0));
for(int i=1; i<20; i++){
for(int j=0; j<n; j++){
Lp[j][i]=Lp[Lp[j][i-1]][i-1]; Rp[j][i]=Rp[Rp[j][i-1]][i-1];
}
}
for(int i=0; i<n; i++) arr[lidx[i][0]]=ridx[i][0];
MST.push_back({0, N-1, -1, -1, ex});
init();
for(int i=0; i<q; i++){
int s=S[i], e=E[i], l=L[i], r=R[i];
//cout<<s<<" "<<e<<" "<<l<<" "<<r<<endl;
for(int i=19; i>=0; i--){
if(l<=Lp[s][i]) s=Lp[s][i];
if(Rp[e][i]<=r) e=Rp[e][i];
}
//cout<<s<<" "<<e<<" "<<l<<" "<<r<<endl;
if(check(0, lidx[s][0], lidx[s][1], ridx[e][0], ridx[e][1])){
ans.push_back(1);
}else ans.push_back(0);
}
return ans;
}
Compilation message
werewolf.cpp: In function 'void ldfs(int)':
werewolf.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<lgp[x].size(); i++){
~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void rdfs(int)':
werewolf.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<rgp[x].size(); i++){
~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void init()':
werewolf.cpp:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i1==MST[MST[x].l].v.size() && i2==MST[MST[x].r].v.size()) break;
~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:88:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i1==MST[MST[x].l].v.size() && i2==MST[MST[x].r].v.size()) break;
~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i1==MST[MST[x].l].v.size()){
~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:91:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
}else if(i2==MST[MST[x].r].v.size()){
~~^~~~~~~~~~~~~~~~~~~~~~~~
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:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<gp[i].size(); j++){
~^~~~~~~~~~~~~
werewolf.cpp:143:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<gp[i].size(); j++){
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
14456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
14456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
615 ms |
120380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
14456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
