Submission #84639

#	Time	Username	Problem	Language	Result	Execution time	Memory
84639		KLPP	Werewolf (IOI18_werewolf)	C++14	15 / 100	4038 ms	357408 KiB

werewolf

#include "werewolf.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pii;
class DSU{
	int parent[1000000];
	int root[1000000];
	int ST[1000000][32];
	vector<int> child[1000000];
	int TOP;
	int MOD;
	int N;
	public:
	vector<int> Tour;
	int first[1000000];
	int last[1000000];
	void init(int n, int mod){
		N=n;
		for(int i=0;i<n;i++){
			parent[i]=i;
			root[i]=i;
			first[i]=-1;
			last[i]=-1;
		}
		MOD=mod;
	}
	int Root(int x){
		if(x==root[x])return x;
		root[x]=Root(root[x]);
		return root[x];
	}
	void merge(int a, int b){
		a=Root(a);
		b=Root(b);
		if(a==b)return;
		if(MOD){
			if(a<b){
				parent[a]=b;
				root[a]=b;
			}else{
				parent[b]=a;
				root[b]=a;
			}
			return;
		}
		if(a<b){
			parent[b]=a;
			root[b]=a;
		}else{
			parent[a]=b;
			root[a]=b;
		}
		return;
	}
	void arrange(){
		for(int i=0;i<N;i++){
			if(parent[i]!=i){
				child[parent[i]].push_back(i);
			}else TOP=i;
		}
		for(int i=0;i<N;i++){
			ST[i][0]=parent[i];
		}
		for(int j=1;j<32;j++){
			for(int i=0;i<N;i++){
				ST[i][j]=ST[ST[i][j-1]][j-1];
			}
		}
	}
	void DFS(int node){
		first[node]=Tour.size();
		Tour.push_back(node);
		for(int i=0;i<child[node].size();i++){
			DFS(child[node][i]);
			//Tour.push_back(node);
		}
		last[node]=Tour.size();
	}
	void START(){
		DFS(TOP);
	}
	int Query(int Start,int Top){
		if(MOD==0){
			int ans=Start;
			for(int i=31;i>-1;i--){
				if(ST[ans][i]>=Top)ans=ST[ans][i];
			}
			return ans;
		}
		int ans=Start;
		for(int i=31;i>-1;i--){
			if(ST[ans][i]<=Top)ans=ST[ans][i];
		}
		return ans;
	}
	void CMP(){
		for(int i=0;i<Tour.size();i++){
			if(first[Tour[i]]==-1)first[Tour[i]]=i;
			last[Tour[i]]=i;
		}
	}
	void print(){
		/*for(int i=0;i<N;i++){
			cout<<parent[i]<<" ";
		}cout<<endl;*/
		for(int i=0;i<Tour.size();i++){
			cout<<Tour[i]<<" ";
		}cout<<endl;
	}

};
DSU *D1;
DSU *D2;
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();
	std::vector<int> A(Q);
	D1=new DSU();D2=new DSU();
	D1->init(N,0);
	D2->init(N,1);
	vector<pair<int,int> > order1;
	vector<pair<int,int> > order2;
	for(int i=0;i<X.size();i++){
		if(X[i]<Y[i]){
			order1.push_back(pii(X[i],Y[i]));
			order2.push_back(pii(Y[i],X[i]));
		}
		else{
			order1.push_back(pii(Y[i],X[i]));
			order2.push_back(pii(X[i],Y[i]));
		}
	}
	sort(order1.begin(),order1.end());
	sort(order2.begin(),order2.end());
	for(int i=order1.size()-1;i>-1;i--){
		//cout<<order1[i].first<<" "<<order1[i].second<<endl;
		D1->merge(order1[i].first,order1[i].second);
	}D1->arrange();
	D1->START();
	//D1->CMP();
	//D1->print();
	for(int i=0;i<order2.size();i++){
		D2->merge(order2[i].first,order2[i].second);
	}
	D2->arrange();
	D2->START();
	//D2->CMP();
	//D2->print();
	int Queries[Q][4];
	for(int i=0;i<Q;i++){
		Queries[i][0]=D1->first[D1->Query(S[i],L[i])];
		Queries[i][1]=D1->last[D1->Query(S[i],L[i])];
		Queries[i][2]=D2->first[D2->Query(E[i],R[i])];
		Queries[i][3]=D2->last[D2->Query(E[i],R[i])];
		//cout<<D2->Query(E[i],R[i])<<" ";
	}//cout<<endl;
	
	
	for (int i = 0; i < Q; ++i) {//cout<<i<<endl;
		A[i] = 0;
		
		/*for(int x=Queries[i][0];x<Queries[i][1];x++){
			for(int y=Queries[i][2];y<Queries[i][3];y++){
				if(D1->Tour[x]==D2->Tour[y])A[i]=1;
			}
		}*/
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<Q;j++){
			if(Queries[j][0]<=D1->first[i] && D1->first[i]<Queries[j][1] && Queries[j][2]<=D2->first[i] && D2->first[i]<Queries[j][3]){
				A[j]=1;//cout<<j<<" "<<i<<endl;
			}
		}
	}
	return A;
}

Compilation message (stderr)

werewolf.cpp: In member function 'void DSU::DFS(int)':
werewolf.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<child[node].size();i++){
               ~^~~~~~~~~~~~~~~~~~~
werewolf.cpp: In member function 'void DSU::CMP()':
werewolf.cpp:100:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<Tour.size();i++){
               ~^~~~~~~~~~~~
werewolf.cpp: In member function 'void DSU::print()':
werewolf.cpp:109:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<Tour.size();i++){
               ~^~~~~~~~~~~~
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:127:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
werewolf.cpp:146:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<order2.size();i++){
              ~^~~~~~~~~~~~~~

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