oj.uz

Submission #84806

# Submission time Handle Problem Language Result Execution time Memory
84806 2018-11-17T09:57:13 Z KLPP Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 487796 KB 
#include "werewolf.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pii;
typedef std::map<pii,int>::iterator mit;
class DFT{
	map<pii,int> m;
	int N;
	public:
	void init(int n){
		N=n;
	}
	void sum(int a, int b, int x){
		mit it =m.find(pii(a,b));
		if(it==m.end()){
			m[pii(a,b)]=x;
			return;
		}
		m[pii(a,b)]=it->second+x;
	}
	int get(int a, int b){
		mit it =m.find(pii(a,b));
		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;
	
	
	/*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:117: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:141: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:150: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:169:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
werewolf.cpp:188: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 271 ms 329208 KB Output is correct
2 Correct 275 ms 329264 KB Output is correct
3 Correct 275 ms 329264 KB Output is correct
4 Correct 270 ms 329336 KB Output is correct
5 Correct 282 ms 329352 KB Output is correct
6 Correct 272 ms 329360 KB Output is correct
7 Correct 272 ms 329360 KB Output is correct
8 Correct 270 ms 329368 KB Output is correct
9 Correct 272 ms 329372 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 329208 KB Output is correct
2 Correct 275 ms 329264 KB Output is correct
3 Correct 275 ms 329264 KB Output is correct
4 Correct 270 ms 329336 KB Output is correct
5 Correct 282 ms 329352 KB Output is correct
6 Correct 272 ms 329360 KB Output is correct
7 Correct 272 ms 329360 KB Output is correct
8 Correct 270 ms 329368 KB Output is correct
9 Correct 272 ms 329372 KB Output is correct
10 Correct 368 ms 333584 KB Output is correct
11 Correct 372 ms 333584 KB Output is correct
12 Correct 355 ms 333584 KB Output is correct
13 Correct 364 ms 334264 KB Output is correct
14 Correct 390 ms 334492 KB Output is correct
15 Correct 357 ms 334492 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 329208 KB Output is correct
2 Correct 275 ms 329264 KB Output is correct
3 Correct 275 ms 329264 KB Output is correct
4 Correct 270 ms 329336 KB Output is correct
5 Correct 282 ms 329352 KB Output is correct
6 Correct 272 ms 329360 KB Output is correct
7 Correct 272 ms 329360 KB Output is correct
8 Correct 270 ms 329368 KB Output is correct
9 Correct 272 ms 329372 KB Output is correct
10 Correct 368 ms 333584 KB Output is correct
11 Correct 372 ms 333584 KB Output is correct
12 Correct 355 ms 333584 KB Output is correct
13 Correct 364 ms 334264 KB Output is correct
14 Correct 390 ms 334492 KB Output is correct
15 Correct 357 ms 334492 KB Output is correct
16 Execution timed out 4123 ms 487796 KB Time limit exceeded
17 Halted 0 ms 0 KB -