#include "werewolf.h"
#include <vector>
#include <algorithm>
#include <deque>
#include <iostream>
using namespace std;
#define MAX_N 20
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];
void init(int x){
if(MST[x].s==MST[x].e){
MST[x].v.push_back(arr[MST[x].s]); return;
}
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});
init(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});
init(MST[x].r);
}
int i1=0, i2=0;
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++]);
}
}
}
}
deque<int> dq;
ST now;
bool check(int x, int y, int z, int w){
while(!dq.empty()) dq.pop_back();
dq.push_back(0);
while(!dq.empty()){
now=MST[dq.front()]; dq.pop_front();
if(!(now.s>y || now.e<x)){
if(x<=now.s && now.e<=y){
vector<int>::iterator it = lower_bound(now.v.begin(), now.v.end(), z);
if(it!=now.v.end() && *it<=w) return true;
}else{
if(now.s!=now.e){
dq.push_back(now.l); dq.push_back(now.r);
}
}
}
}
return false;
}
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(0);
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(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(int)':
werewolf.cpp:77:14: 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:77:44: 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:78:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i1==MST[MST[x].l].v.size()){
~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:80:20: 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:125:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<gp[i].size(); j++){
~^~~~~~~~~~~~~
werewolf.cpp:136:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<gp[i].size(); j++){
~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
164 ms |
27740 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
