oj.uz

Submission #84817

# Submission time Handle Problem Language Result Execution time Memory
84817 2018-11-17T10:18:23 Z KLPP Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 509752 KB 
#include "werewolf.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_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 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;
DFT *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 DFT();
	F->init(N);
	for(int i=0;i<N;i++){
		F->at(D1->first[i]+1,D2->first[i]+1,1);
	}
	for(int i=0;i<Q;i++){
		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])];
		A[i]=F->query(Query[i][0],Query[i][2])+F->query(Query[i][1],Query[i][3])-F->query(Query[i][0],Query[i][3])-F->query(Query[i][1],Query[i][2]);
		if(A[i]>0)A[i]=1;
		//cout<<D2->Query(E[i],R[i])<<" ";
	}//cout<<endl;
	//cout<<F->query(N,N)<<endl;
	
	
	/*for (int i = 0; i < Q; ++i) {//cout<<i<<endl;
		A[i] = 0;
		
		
	}
	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

werewolf.cpp: In member function 'void DSU::DFS(int)':
werewolf.cpp:119: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:143: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:152: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:171:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
werewolf.cpp:190:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<order2.size();i++){
              ~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 329216 KB Output is correct
2 Correct 273 ms 329332 KB Output is correct
3 Correct 280 ms 329408 KB Output is correct
4 Correct 273 ms 329408 KB Output is correct
5 Correct 274 ms 329468 KB Output is correct
6 Correct 273 ms 329528 KB Output is correct
7 Correct 285 ms 329572 KB Output is correct
8 Correct 272 ms 329572 KB Output is correct
9 Correct 273 ms 329572 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 329216 KB Output is correct
2 Correct 273 ms 329332 KB Output is correct
3 Correct 280 ms 329408 KB Output is correct
4 Correct 273 ms 329408 KB Output is correct
5 Correct 274 ms 329468 KB Output is correct
6 Correct 273 ms 329528 KB Output is correct
7 Correct 285 ms 329572 KB Output is correct
8 Correct 272 ms 329572 KB Output is correct
9 Correct 273 ms 329572 KB Output is correct
10 Correct 312 ms 332316 KB Output is correct
11 Correct 312 ms 332316 KB Output is correct
12 Correct 319 ms 332316 KB Output is correct
13 Correct 309 ms 332560 KB Output is correct
14 Correct 322 ms 332680 KB Output is correct
15 Correct 307 ms 332680 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4098 ms 509752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 329216 KB Output is correct
2 Correct 273 ms 329332 KB Output is correct
3 Correct 280 ms 329408 KB Output is correct
4 Correct 273 ms 329408 KB Output is correct
5 Correct 274 ms 329468 KB Output is correct
6 Correct 273 ms 329528 KB Output is correct
7 Correct 285 ms 329572 KB Output is correct
8 Correct 272 ms 329572 KB Output is correct
9 Correct 273 ms 329572 KB Output is correct
10 Correct 312 ms 332316 KB Output is correct
11 Correct 312 ms 332316 KB Output is correct
12 Correct 319 ms 332316 KB Output is correct
13 Correct 309 ms 332560 KB Output is correct
14 Correct 322 ms 332680 KB Output is correct
15 Correct 307 ms 332680 KB Output is correct
16 Execution timed out 4098 ms 509752 KB Time limit exceeded
17 Halted 0 ms 0 KB -