이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>adj1[3005];
vector<int>adj2[3005];
vector<int>adj3[200001];
bool b=false;
bool vis1[3005];
bool vis2[3005];
bool vis3[200001];
int cnt[200001];
vector<int>v;
int rv[200001];
int seg1[600000];
int seg2[600000];
void dfs1(int cur,int par){
vis1[cur]=1;
for(int i:adj1[cur]){
if(i!=par&&!vis1[i]){
dfs1(i,cur);
}
}
}
void dfs2(int cur,int par){
vis2[cur]=1;
if(vis1[cur]){
b=true;
return;
}
for(int i:adj2[cur]){
if(i!=par&&!vis2[i]){
dfs2(i,cur);
}
}
}
void dfs3(int cur,int par){
vis3[cur]=1;
for(int i:adj3[cur]){
if(i!=par&&!vis3[i]){
v.push_back(i);
rv[i]=v.size()-1;
dfs3(i,cur);
}
}
}
void build1(int L,int R,int node){
if(L==R){
seg1[node]=v[L];
return;
}
build1(L,(L+R)/2,2*node);
build1((L+R)/2+1,R,2*node+1);
seg1[node]=min(seg1[2*node],seg1[2*node+1]);
}
void build2(int L,int R,int node){
if(L==R){
seg2[node]=v[L];
return;
}
build2(L,(L+R)/2,2*node);
build2((L+R)/2+1,R,2*node+1);
seg2[node]=max(seg2[2*node],seg2[2*node+1]);
}
int query1(int A,int B,int L,int R,int node){
if(R<A||B<L){
return 1e9;
}
else if(A<=L&&B>=R){
return seg1[node];
}
else{
return min(query1(A,B,L,(L+R)/2,2*node),query1(A,B,(L+R)/2+1,R,2*node+1));
}
}
int query2(int A,int B,int L,int R,int node){
if(R<A||B<L){
return -1e9;
}
else if(A<=L&&B>=R){
return seg2[node];
}
else{
return max(query2(A,B,L,(L+R)/2,2*node),query2(A,B,(L+R)/2+1,R,2*node+1));
}
}
int bsearch1(int s,int e,int l,bool b){
if(b&&query1(s,e,0,v.size()-1,1)>=l){
return e+1;
}
if(!b&&query1(e,s,0,v.size()-1,1)>=l){
return e-1;
}
if(b){
int m=(s+e)/2;
if(e-s<=1){
if(v[s]<l){
return s;
}
return e;
}
if(query1(s,m,0,v.size()-1,1)<l){
return bsearch1(s,m,l,b);
}
return bsearch1(m,e,l,b);
}
else{
int m=(s+e)/2;
if(s-e<=1){
if(v[s]<l){
return s;
}
return e;
}
if(query1(m,s,0,v.size()-1,1)<l){
return bsearch1(m,s,l,b);
}
return bsearch1(e,m,l,b);
}
}
int bsearch2(int s,int e,int r,bool b){
if(b&&query2(s,e,0,v.size()-1,1)<=r){
return s-1;
}
if(!b&&query2(e,s,0,v.size()-1,1)<=r){
return s+1;
}
if(b){
//search from right
int m=(s+e)/2;
if(e-s<=1){
if(v[e]>r){
return e;
}
return s;
}
if(query2(m,e,0,v.size()-1,1)>r){
return bsearch2(m,e,r,b);
}
return bsearch2(s,m,r,b);
}
else{
int m=(s+e)/2;
if(s-e<=1){
if(v[e]>r){
return e;
}
return s;
}
if(query2(e,m,0,v.size()-1,1)>r){
return bsearch2(e,m,r,b);
}
return bsearch2(m,s,r,b);
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
vector<int>ans;
if(N>=3000){
for(int i=0;i<L.size();i++){
memset(vis1,0,sizeof vis1);
memset(vis2,0,sizeof vis2);
int l=L[i],r=R[i],s=S[i],e=E[i];
for(int j=0;j<=3000;j++){
adj1[j].clear();
adj2[j].clear();
}
for(int j=0;j<X.size();j++){
if(X[j]>=l&&Y[j]>=l){
adj1[X[j]].push_back(Y[j]);
adj1[Y[j]].push_back(X[j]);
}
if(X[j]<=r&&Y[j]<=r){
adj2[X[j]].push_back(Y[j]);
adj2[Y[j]].push_back(X[j]);
}
}
b=false;
dfs1(s,3003);
dfs2(e,3003);
if(b){
ans.push_back(1);
}
else{
ans.push_back(0);
}
}
}
else{
for(int i=0;i<X.size();i++){
cnt[X[i]]++;
cnt[Y[i]]++;
adj3[X[i]].push_back(Y[i]);
adj3[Y[i]].push_back(X[i]);
}
for(int i=0;i<N;i++){
if(cnt[i]==1){
v.push_back(i);
rv[i]=0;
break;
}
}
dfs3(v[0],200005);
build1(0,N-1,1);
build2(0,N-1,1);
for(int i=0;i<S.size();i++){
int s=rv[S[i]],e=rv[E[i]],l=L[i],r=R[i];
bool b=false;
if(s<e){
b=true;
}
int x=bsearch1(s,e,l,b);
int y=bsearch2(s,e,r,b);
cout<<x<<" "<<y<<"\n";
if(b){
x--;
y++;
}
else{
x++;
y--;
}
cout<<x<<" "<<y<<"\n";
if(b^(x>=y)){
ans.push_back(0);
}
else{
ans.push_back(1);
}
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
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:160:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<L.size();i++){
~^~~~~~~~~
werewolf.cpp:168:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<X.size();j++){
~^~~~~~~~~
werewolf.cpp:190:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<X.size();i++){
~^~~~~~~~~
werewolf.cpp:206:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<S.size();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... |