oj.uz

Submission #88843

# Submission time Handle Problem Language Result Execution time Memory
88843 2018-12-09T08:25:33 Z dsjong Werewolf (IOI18_werewolf) C++14
15 / 100
 2462 ms 41900 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(query1(s,e,0,v.size()-1,1)>=l){
		if(b) return e+1;
		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(query2(s,e,0,v.size()-1,1)<=r){
		if(b) return s-1;
		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);
			if(b){
				x--;
				y++;
			}
			else{
				x++;
				y--;
			}
			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:156:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<L.size();i++){
               ~^~~~~~~~~
werewolf.cpp:164:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<X.size();j++){
                ~^~~~~~~~~
werewolf.cpp:186:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<X.size();i++){
               ~^~~~~~~~~
werewolf.cpp:202:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<S.size();i++){
               ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 7 ms 5340 KB Output is correct
3 Correct 7 ms 5340 KB Output is correct
4 Correct 7 ms 5340 KB Output is correct
5 Correct 7 ms 5340 KB Output is correct
6 Correct 7 ms 5340 KB Output is correct
7 Correct 8 ms 5340 KB Output is correct
8 Correct 8 ms 5412 KB Output is correct
9 Correct 7 ms 5452 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 7 ms 5340 KB Output is correct
3 Correct 7 ms 5340 KB Output is correct
4 Correct 7 ms 5340 KB Output is correct
5 Correct 7 ms 5340 KB Output is correct
6 Correct 7 ms 5340 KB Output is correct
7 Correct 8 ms 5340 KB Output is correct
8 Correct 8 ms 5412 KB Output is correct
9 Correct 7 ms 5452 KB Output is correct
10 Correct 569 ms 5948 KB Output is correct
11 Correct 479 ms 5948 KB Output is correct
12 Correct 367 ms 6000 KB Output is correct
13 Correct 675 ms 6024 KB Output is correct
14 Correct 488 ms 6024 KB Output is correct
15 Correct 1386 ms 6156 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 7 ms 5340 KB Output is correct
3 Correct 7 ms 5340 KB Output is correct
4 Correct 7 ms 5340 KB Output is correct
5 Correct 7 ms 5340 KB Output is correct
6 Correct 7 ms 5340 KB Output is correct
7 Correct 8 ms 5340 KB Output is correct
8 Correct 8 ms 5412 KB Output is correct
9 Correct 7 ms 5452 KB Output is correct
10 Correct 569 ms 5948 KB Output is correct
11 Correct 479 ms 5948 KB Output is correct
12 Correct 367 ms 6000 KB Output is correct
13 Correct 675 ms 6024 KB Output is correct
14 Correct 488 ms 6024 KB Output is correct
15 Correct 1386 ms 6156 KB Output is correct
16 Incorrect 2462 ms 41900 KB Output isn't correct
17 Halted 0 ms 0 KB -