이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "werewolf.h"
using namespace std;
#include <vector>
#include <cmath>
#define INF 999999999
struct node{
int x;
vector<int> v;
bool g,h;
node(){}
};
vector<node> v;
std::vector<int> sub1(int n, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R) {
v.resize(n);
for (int i=0;i<X.size();i++){
v[X[i]].v.push_back(Y[i]);
v[Y[i]].v.push_back(X[i]);
}
vector<int> q;
vector<int> z;
z.resize(S.size());
int p;
bool f;
for (int _=0;_<S.size();_++){
for (int i=0;i<n;i++){v[i].g=false;v[i].h=false;}
q.clear();
q.push_back(S[_]);
f=false;
while (!q.empty()){
p=q[q.size()-1];
q.pop_back();
if (v[p].g||p<L[_]){continue;}
v[p].g=true;
for (int i:v[p].v){
q.push_back(i);
}
}
q.clear();
q.push_back(E[_]);
while (!q.empty()){
p=q[q.size()-1];
q.pop_back();
if (v[p].h||p>R[_]){continue;}
if (v[p].g){f=true;break;}
v[p].h=true;
for (int i:v[p].v){
q.push_back(i);
}
}
z[_]=f;
}
return z;
}
struct seg{
int s,x,y,z;
seg(){}
seg(int _x,int _z){
s=INF;x=_x;z=_z;y=(x+z)/2;
}
};
struct segtree{
int n;
vector<seg> v;
segtree(){}
segtree(int _n){
n=pow(2,ceil(log2(_n)));
v.resize(n*2);
v[1]=seg(0,n);
for (int i=2;i<n*2;i++){
if (i%2==0){v[i]=seg(v[i/2].x,v[i/2].y);}
else{v[i]=seg(v[i/2].y,v[i/2].z);}
}
}
void update(int i,int s){
i+=n;
v[i].s=s;
while (i!=1){
i/=2;
v[i].s=min(v[i*2].s,v[i*2+1].s);
}
}
int query(int a,int b,int i){
if (a>=b){return INF;}
if (a==v[i].x&&b==v[i].z){return v[i].s;}
return min(query(a,min(b,v[i].y),i*2),query(max(a,v[i].y),b,i*2+1));
}
int walk(int a,int s){
int i=a+n;
if (v[1].s>=s){return INF;}
i/=2;
while (v[i*2+1].s>=s){
i/=2;
}
i=i*2+1;
while (v[i].x+1!=v[i].z){
if (v[i*2].s<s){
i*=2;
}else{
i=i*2+1;
}
}
return i-n;
}
};
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
if (n<=3000 && X.size()<=6000 and S.size()<=3000){return sub1(n,X,Y,S,E,L,R);}
vector<int> w;
vector<int> m;
vector<vector<int>> raw;
raw.resize(n);
for (int i=0;i<n-1;i++){
raw[X[i]].push_back(Y[i]);
raw[Y[i]].push_back(X[i]);
}
int x,y;
for (int i=0;i<n;i++){
if (raw[i].size()==1){x=i;break;}
}
y=-1;
for (int i=0;i<n-1;i++){
w.push_back(x);
if (raw[x][0]==y){y=x;x=raw[x][1];}
else{y=x;x=raw[x][0];}
}
w.push_back(x);
segtree pos=segtree(n);
segtree neg=segtree(n);
m.resize(n);
for (int i=0;i<n;i++){
pos.update(i,w[i]);
neg.update(i,-w[i]);
m[w[i]]=i;
}
int a,b,l,r;
bool f;
vector<int> z;
for (int i=0;i<S.size();i++){//print(i);
a=S[i];b=E[i];l=L[i];r=R[i];
f=true;
a=m[a];
b=m[b];
if (a<b){
a=pos.walk(a,l);//print(a);print(b);
if (a>b){a=b+1;}
if (w[a-1]>r){f=false;}
if (neg.query(a,b,1)<-r){f=false;}
}else{
b=neg.walk(b,-r);//print(a);print(b);
if (b>a){b=a+1;}//print(a);print(b);
if (w[b-1]<l){f=false;}
if (pos.query(b,a,1)<l){f=false;}
}
z.push_back(f);
}
return z;
}
컴파일 시 표준 에러 (stderr) 메시지
werewolf.cpp: In function 'std::vector<int> sub1(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:15:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for (int i=0;i<X.size();i++){
| ~^~~~~~~~~
werewolf.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int _=0;_<S.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:139:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for (int i=0;i<S.size();i++){//print(i);
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |