제출 #165354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
165354		tneluccus	늑대인간 (IOI18_werewolf)	C++14	100 / 100	923 ms	97392 KiB

werewolf

#include<bits/stdc++.h>
using namespace std;
#define N cac
const int N=2e5+2;
vector<int> head[N];
int posL[N],bit[N],posR[N];
pair<int,int> idxL[N],idxR[N];
vector<int> adj[N];
vector<pair<int,int> > queryL[N],queryR[N],edgeL[N],edgeR[N];
vector<pair<pair<int,int>,pair<int,bool> > > lis[N]; 
void upd(int pos){
	while(pos<N){
		bit[pos]++;
		pos+=(pos&-pos);
	}
}
int get(int pos){
	int sum=0;
	while(pos){
		sum+=bit[pos];
		pos-=(pos&-pos);
	}
	return sum;
}
int getsum(int x,int y){
	return get(y)-get(x-1);
}
int findd(int x){
	if(head[x].size()>1){
		return x;
	}
	if(head[x][0]==x){
		return x;
	}
	int y=findd(head[x][0]);
	head[x][0]=y;
	return y;
}
void unionn(int x,int y){
	x=findd(x),y=findd(y);
	if(head[x].size()<head[y].size()){
		swap(x,y);
	}
	for(int i:head[y]){
		head[x].push_back(i);
	}
	head[y].clear();
	head[y].push_back(x);
}
bool samee(int x,int y){
	return findd(x)==findd(y);
}
#undef N
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 i,j,k,l,n=N,m=X.size(),q=S.size();
	vector<int> ans(q);
	for(i=0;i<m;i++){
		edgeL[min(X[i],Y[i])].push_back({X[i],Y[i]});
		edgeR[max(X[i],Y[i])].push_back({X[i],Y[i]});
	}
	for(i=0;i<n;i++){
		head[i].push_back(i);
	}
	for(i=0;i<q;i++){
		queryL[L[i]].push_back({S[i],i});
		queryR[R[i]].push_back({E[i],i});
	}
	for(i=n-1;i>-1;i--){
		for(auto x:edgeL[i]){
			if(!samee(x.first,x.second)){
				unionn(x.first,x.second);
			}
		}
		for(auto x:queryL[i]){
			j=findd(x.first);
//			cout<<x.second<<'\n';
//			for(int y:head[j]){
//				cout<<y<<' ';
//			}
//			cout<<'\n';
			idxL[x.second]={head[j][0],head[j].back()};
		}
	}
	j=findd(1);
	assert(head[j].size()==n);
	for(i=0;i<n;i++){
		posL[head[j][i]]=i;
	}
	for(i=0;i<n;i++){
		head[i].clear();
		head[i].push_back(i);
	}
	for(i=0;i<n;i++){
		for(auto x:edgeR[i]){
			if(!samee(x.first,x.second)){
				unionn(x.first,x.second);
			}
		}
		for(auto x:queryR[i]){
			j=findd(x.first);
//			cout<<x.second<<'\n';
//			for(int y:head[j]){
//				cout<<y<<' ';
//			}
//			cout<<'\n';
			idxR[x.second]={head[j][0],head[j].back()};
		}
	}
	j=findd(1);
	assert(head[j].size()==n);
	for(i=0;i<n;i++){
		posR[head[j][i]]=i;
	}
	for(i=0;i<q;i++){
		idxL[i]={posL[idxL[i].first],posL[idxL[i].second]};
		idxR[i]={posR[idxR[i].first],posR[idxR[i].second]};
		assert(idxL[i].first<=idxL[i].second);
		assert(idxR[i].first<=idxR[i].second);
		lis[idxR[i].second].push_back({idxL[i],{i,true}});
		if(idxR[i].first){
			lis[idxR[i].first-1].push_back({idxL[i],{i,false}});
		}
	}
	for(i=0;i<n;i++){
		upd(posL[head[j][i]]+1);
		for(auto x:lis[i]){
			if(!x.second.second){
				ans[x.second.first]-=getsum(x.first.first+1,x.first.second+1);
			}
			else{
				ans[x.second.first]+=getsum(x.first.first+1,x.first.second+1);
			}
		}
	}
	for(i=0;i<q;i++){
//		cout<<ans[i]<<endl;
		if(ans[i]>0){
			ans[i]=1;
		}
	}
	return ans;
}
//int main(){
//	vector<int> oh=check_validity({6},{5,1,1,3,3,5},{1,2,3,4,0,2},{4,4,5,3},{2,2,4,4},{1,2,3,3},{2,2,4,4});
//	cout<<oh.size()<<" ANS"<<endl;
//	for(int i:oh){
//		cout<<i<<'\n';
//	}
//}

컴파일 시 표준 에러 (stderr) 메시지

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from werewolf.cpp:1:
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:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(head[j].size()==n);
         ~~~~~~~~~~~~~~^~~
werewolf.cpp:110:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(head[j].size()==n);
         ~~~~~~~~~~~~~~^~~
werewolf.cpp:55:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,l,n=N,m=X.size(),q=S.size();
          ^
werewolf.cpp:55:12: warning: unused variable 'l' [-Wunused-variable]
  int i,j,k,l,n=N,m=X.size(),q=S.size();
            ^

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