Submission #84824

#	Time	Username	Problem	Language	Result	Execution time	Memory
84824		KLPP	Werewolf (IOI18_werewolf)	C++14	100 / 100	1506 ms	504632 KiB

werewolf

#include "werewolf.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<map>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pii;
typedef std::unordered_map<lld,int>::const_iterator mit;
/*class DFT{
	std::unordered_map<lld,int> m;
	int N;
	public:
	void init(int n){
		N=n;
		//m.rehash(10000);
	}
	void sum(int a, int b, int x){
		lld pos=a*(N+1)+b;
		mit it =m.find(pos);
		if(it==m.end()){
			m[pos]=x;
			return;
		}
		m[pos]=it->second+x;
	}
	int get(int a, int b){lld pos=a*(N+1)+b;
		mit it =m.find(pos);
		if(it==m.end()){
			return 0;
		}
		return it->second;
	}
	void at(int x, int y, int up){
		for(int i=x;i<=N;i+=(i&(-i))){
			for(int j=y;j<=N;j+=(j&(-j))){
				sum(i,j,up);
			}
		}
	}
	int query(int x, int y){
		int ans=0;
		for(int i=x;i>0;i-=(i&(-i))){
			for(int j=y;j>0;j-=(j&(-j))){
				ans+=get(i,j);
			}
		}return ans;
	}
};*/
class FT{
	int arr[1000000];
	int N;
	public:
	void init(int n){
		N=n;
		//m.rehash(10000);
		for(int i=0;i<=n;i++)arr[i]=0;
	}
	void at(int x, int up){
		for(int i=x;i<=N;i+=(i&(-i))){
			arr[i]+=up;
		}
	}
	int query(int x){
		int ans=0;
		for(int i=x;i>0;i-=(i&(-i))){
			ans+=arr[i];
		}return ans;
	}
};

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;
FT *F;
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 Query[Q][4];
	F=new FT();
	F->init(N);
	int per[N];
	for(int i=0;i<N;i++){
		per[D1->first[i]]=D2->first[i]+1;
	}
	/*for(int i=0;i<N;i++){
		cout<<per[i]<<endl;
	}*/
	vector<pair<pii,int> >V;
	for(int i=0;i<Q;i++){A[i]=0;
		Query[i][0]=D1->first[D1->Query(S[i],L[i])];
		Query[i][1]=D1->last[D1->Query(S[i],L[i])];
		Query[i][2]=D2->first[D2->Query(E[i],R[i])];
		Query[i][3]=D2->last[D2->Query(E[i],R[i])];
		V.push_back(pair<pii,int>(pii(Query[i][0],Query[i][2]),4*i));
		V.push_back(pair<pii,int>(pii(Query[i][1],Query[i][3]),4*i+1));
		V.push_back(pair<pii,int>(pii(Query[i][0],Query[i][3]),4*i+2));
		V.push_back(pair<pii,int>(pii(Query[i][1],Query[i][2]),4*i+3));
	}
	sort(V.begin(),V.end());
	int pnt=0;
	for(int i=0;i<V.size();i++){
		//cout<<V[i].first.first<<" "<<V[i].first.second<<" "<<V[i].second<<endl;
		while(pnt<V[i].first.first){
			pnt++;
			F->at(per[pnt-1],1);
		}
		if((V[i].second%4)<2){
			A[V[i].second/4]+=F->query(V[i].first.second);
		}else{
			A[V[i].second/4]-=F->query(V[i].first.second);
		}
	}
	
	
	
	for (int i = 0; i < Q; ++i) {//cout<<i<<endl;
		if(A[i]>0)A[i]=1;
	}
	
	return A;
}

Compilation message (stderr)

werewolf.cpp: In member function 'void DSU::DFS(int)':
werewolf.cpp:141: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:165: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:174: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:193:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
werewolf.cpp:212:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<order2.size();i++){
              ~^~~~~~~~~~~~~~
werewolf.cpp:242:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<V.size();i++){
              ~^~~~~~~~~

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