oj.uz

Submission #88849

# Submission time Handle Problem Language Result Execution time Memory
88849 2018-12-09T08:44:20 Z dsjong Werewolf (IOI18_werewolf) C++14
0 / 100
 217 ms 29084 KB 
#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;
}

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: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++){
               ~^~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 5244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 5244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 217 ms 29084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 5244 KB Output isn't correct
2 Halted 0 ms 0 KB -