제출 #135260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
135260		amiratou	늑대인간 (IOI18_werewolf)	C++14	41 / 100	1746 ms	27640 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));
}
int D,LE,RE;
int vis_dfs[5001],v=1;
int dp[101][2][2];
int dfs(int node,int changed,int trans){
	//cerr<<node<<" "<<changed<<" "<<trans<<"\n";
	if(node==D&&!changed&&trans)return 1;
	if(node==D)return changed;
	if(dp[node][changed][trans]!=-1)
		return dp[node][changed][trans];
	vis_dfs[node]=1;
	int ans=0;
	for(auto child:vec[node]){
		if(vis_dfs[child]==1)continue;
		if(child<LE&&!changed){
			if(trans)ans|=dfs(child,1,0);
			else continue;
		}
		if(child>RE&&changed)continue;
		if(child<=RE&&changed)ans|=dfs(child,1,0);
		if(child>=LE&&!changed)ans|=dfs(child,0,((child>=LE&&child<=RE)));
		if(trans&&child<=RE&&!changed)ans|=dfs(child,1,0);
		if(ans){vis_dfs[node]=0; return dp[node][changed][trans]=1;}
	}
	vis_dfs[node]=0;
	return dp[node][changed][trans]=0;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
	int M = X.size();
	int Q = S.size();
	vec.resize(N);
	for (int i = 0; i < X.size(); ++i)
	{
		vec[X[i]].pb(Y[i]);
		vec[Y[i]].pb(X[i]);
	}
	if(N<=100||M<=200||Q<=100){
		vector<int> res(Q);
		for (int i =0; i < Q; ++i)
		{
			memset(dp,-1,sizeof dp);
			D=E[i];
			LE=L[i],RE=R[i];
			//cerr<<S[i]<<","<<E[i]<<"\n";
			//cerr<<L[i]<<","<<R[i]<<"\n";
			if(S[i]<LE||E[i]>RE)res[i]=0;
			else res[i]=dfs(S[i],0,(S[i]>=L[i]&&S[i]<=R[i]));
		}	
		return res;
	}
	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);
	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);
					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]]);
					if(q.se>R[i]){l=med+1;continue;}
				}
				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{
			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;}
				}
				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;
			}		
		}}
	return res;
}

컴파일 시 표준 에러 (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:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X.size(); ++i)
                  ~~^~~~~~~~~~

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