제출 #125544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
125544		chubyxdxd	늑대인간 (IOI18_werewolf)	C++11	15 / 100	2091 ms	46812 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int> > G;
int vish[5000];
int visw[5000];
int vis[400000];
int tree[1000000];
int tree1[1000000];
int a,b;
int v[400000];
int k=0;
int h,h1;
map<ll,ll> mp;
void init1(int node,int l,int r){
	if(l==r) tree[node]=v[l];
	else{
		int mi=(l+r)/2;
		init1(2*node,l,mi);
		init1(2*node+1,mi+1,r);
		tree[node]=max(tree[2*node],tree[2*node+1]);
	}
}
int query1(int x,int y,int node,int l,int r){
	if(r<x or l>y) return -10000;
	if(x<=l and r<=y){
		return tree[node];
	}
	else{
		int mi=(l+r)/2;
		return max(query1(x,y,2*node,l,mi),query1(x,y,2*node+1,mi+1,r));
	}
}
void init2(int node,int l,int r){
	if(l==r) tree1[node]=v[l];
	else{
		int mi=(l+r)/2;
		init2(2*node,l,mi);
		init2(2*node+1,mi+1,r);
		tree1[node]=min(tree1[2*node],tree1[2*node+1]);
	}
}
int query2(int x,int  y,int  node,int l,int r){
	if(r<x or l>y ) return 4000000;
	if(x<=l and r<=y){
		return tree1[node];
	}
	else{
		int mi=(l+r)/2;
		return min(query2(x,y,2*node,l,mi),query2(x,y,2*node+1,mi+1,r));
	}
}
void dfs(int x){
	v[k]=x;
	k++;
	vis[x]=1;
	int tam1=G[x].size();
	for(int i=0;i<tam1;i++){
		int u=G[x][i];
		if(vis[u]==0){
			dfs(u);
		}
	}
}
void dfsh(int x){
	vish[x]=1;
	int taml=G[x].size();
	for(int i=0;i<taml;i++){
		int u=G[x][i];
		if(vish[u]==0 and u>=a){
		dfsh(u);
		//cout<<x<<" "<<1<<endl;
		}
	}
}
void dfsw(int x){
	visw[x]=1;
	int taml=G[x].size();
	for(int i=0;i<taml;i++){
		int u=G[x][i];
		if(visw[u]!=1 and u<=b){
		dfsw(u);
		//cout<<x<<" "<<2<<endl;
		}
	}
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R){	
  int Q = S.size();
  G.clear();
  int tam=X.size();
  G.assign(tam+1,vector<int>());
  for(int i=0;i<tam;i++){
  	G[X[i]].push_back(Y[i]);
  	G[Y[i]].push_back(X[i]);
  }
  //int c1=0;
  //int c2=0;
  int d1;
  for(int i=0;i<tam;i++){
  		if(G[i].size()==1){
  			d1=i;
  			break;
  		}
  }
  std::vector<int> A(Q);
  if(N<=3000 and Q<=3000){
  		for (int i = 0; i < Q; ++i) {
  		memset(vish, 0, sizeof vish);
  		memset(visw, 0,sizeof visw);
  		a=L[i];
  		b=R[i];
  		dfsh(S[i]);
  		dfsw(E[i]);
  		int sw=0;
  		for(int j=0;j<N;j++){
  			if(vish[j]==1 and visw[j]==1){
  				sw=1;	
  				break;
  			}
  		}
  		if(sw==1){
  			A[i]=1;
  		}
  		else{
  			A[i]=0;
  		}
  	
  	}
  	return A;
  }
  		memset(vis, 0, sizeof vis);
 		dfs(d1);
  		for(int i=0;i<N;i++){
  			mp[v[i]]=i;
  			//cout<<v[i]<<" ";
  		}
		//cout<<endl;	
  		init1(1,0,N-1);
  		init2(1,0,N-1);
  		for (int i=0;i<Q;i++) {
  			//int sw=0;
  			int a=min(mp[S[i]],mp[E[i]]);
  			int b=max(mp[S[i]],mp[E[i]]);
  			if(S[i]<L[i] or E[i]>R[i]){
  				A[i]=0;
  				continue;
  			}
  			int low=a,hi=b,mid,sw=0;
  			while(hi-low>1){
  				sw=1;
  				mid=(low+hi)/2;
				int minimo=query2(low,mid,1,0,N-1);
				//cout<<i+1<<":"<<minimo<<endl;
				if(minimo>=L[i])low=mid+1;
				else hi=mid;
  			}
  			//cout<<1<<endl;
  			int maximo;
  			if(sw==1)
  			maximo=query1(hi,b,1,0,N-1);
  			else
  			maximo=query1(low,hi,1,0,N-1);
  			if(maximo<=R[i]){
  				A[i]=1;
  			}
  			else{
  				A[i]=0;
  			}
  		}
  		return A;	
}

컴파일 시 표준 에러 (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:133:7: warning: 'd1' may be used uninitialized in this function [-Wmaybe-uninitialized]
    dfs(d1);
    ~~~^~~~

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