Submission #135179

#	Time	Username	Problem	Language	Result	Execution time	Memory
135179		amiratou	늑대인간 (IOI18_werewolf)	C++14	34 / 100	1666 ms	35960 KiB

werewolf

#pragma GCC optimize("O3")
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
#define INF (int)(1e9)

vector<vector<int> > vec;
int A[200005],idx=0,to_id[200005];
ii st[800005];
bool vis[200005];
void build(int node,int l,int r){
	if(l==r){
		st[node]=ii(A[l],A[l]);
		return ;
	}
	int med=((l+r)>>1);
	build(node<<1,l,med),build((node<<1)+1,med+1,r);
	st[node].fi=min(st[node<<1].fi,st[(node<<1)+1].fi);
	st[node].se=max(st[node<<1].se,st[(node<<1)+1].se);

}
ii query(int node,int l,int r,int i,int j){
	if(l>j||r<i)
		return ii(INF,-1);
	if(l>=i&&r<=j)
		return st[node];
	int med=((l+r)>>1);
	ii q1=query(node<<1,l,med,i,j),q2=query((node<<1)+1,med+1,r,i,j);
	return ii(min(q1.fi,q2.fi),max(q1.se,q2.se));
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {

	vec.resize(N);
	for (int i = 0; i < X.size(); ++i)
	{
		vec[X[i]].pb(Y[i]);
		vec[Y[i]].pb(X[i]);
	}
	int start=0;
	for (int i = 0; i < N; ++i)
		if(vec[i].size()==1){
			start=i;
			break;
		}
	queue<int> AA;
	AA.push(start);
	vis[start]=1;
	while(!AA.empty()){
		int front=AA.front();
		A[idx]=front;
		to_id[front]=idx++;
		AA.pop();
		for(auto child:vec[front])
			if(!vis[child])
				vis[child]=1,AA.push(child);
	}
	build(1,0,idx);
	int Q = S.size();
	vector<int> res(Q);
	fill(res.begin(),res.end(),0);
	for (int i = 0; i < Q; ++i) {
		if(S[i]==E[i]){
			if(S[i]<=R[i]&&S[i]>=L[i])res[i]=1;
			else res[i]=0;
			continue;
		}
		if(S[i]<L[i]||E[i]>R[i]){res[i]=0;continue;}
		if(to_id[S[i]]<to_id[E[i]]){
			int l=to_id[S[i]],r=to_id[E[i]];
			while(l<=r){
				int med=((l+r)>>1);
				if(med!=to_id[S[i]]){
					ii q=query(1,0,idx,to_id[S[i]],med-1);
					//cerr<<q.fi<<" "<<q.se<<"\n";
					if(q.fi<L[i]){r=med-1;continue;}
				}
				if(med!=to_id[E[i]]){
					ii q=query(1,0,idx,med+1,to_id[E[i]]);
					//cerr<<q.fi<<" "<<q.se<<"\n";
					if(q.se>R[i]){l=med+1;continue;}
				}
				//cerr<<L[i]<<" "<<R[i]<<'\n';
				//cerr<<S[i]<<" "<<E[i]<<'\n';
				//cerr<<A[med]<<"\n";
				if(A[med]<=R[i]&&A[med]>=L[i])res[i]=1;
				else if(A[med]>=L[i]){
					if(A[med]==(E[i]))res[i]=0;
					else if(A[med+1]<=R[i]&&A[med+1]>=L[i])res[i]=1;
					else res[i]=0;
				}
				else if(A[med]<=R[i]){
					if(A[med]==S[i])res[i]=0;
					else if(A[med-1]<=R[i]&&A[med-1]>=L[i])res[i]=1;
					else res[i]=0;
				}
				break;
			}
		}
		else{
			//cerr<<2<<" ";
			int l=to_id[E[i]],r=to_id[S[i]];
			while(l<=r){
				int med=((l+r)>>1);
				if(med!=to_id[E[i]]){
					ii q=query(1,0,idx,to_id[E[i]],med-1);
					if(q.se>R[i]){r=med-1;continue;}
				}
				if(med!=to_id[S[i]]){
					ii q=query(1,0,idx,med+1,to_id[S[i]]);
					if(q.fi<L[i]){l=med+1;continue;}
				}
				//cerr<<med<<"-----\n";
				if(A[med]<=R[i]&&A[med]>=L[i])res[i]=1;
				else if(A[med]<=R[i]){
					if(A[med]==(S[i]))res[i]=0;
					else if(A[med+1]<=R[i]&&A[med+1]>=L[i])res[i]=1;
					else res[i]=0;
				}
				else if(A[med]>=L[i]){
					if(A[med]==E[i])res[i]=0;
					else if(A[med-1]<=R[i]&&A[med-1]>=L[i])res[i]=1;
					else res[i]=0;
				}
				break;
			}		
		}
		//cerr<<res[i]<<"\n";
	}
	return res;
}

Compilation message (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:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X.size(); ++i)
                  ~~^~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51