oj.uz

답안 #84814

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
84814 2018-11-17T10:15:09 Z KLPP 늑대인간 (IOI18_werewolf) C++14
15 / 100
 4000 ms 474864 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;
	}
	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:118: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:142: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:151: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:170:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
werewolf.cpp:189: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

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 329336 KB Output is correct
2 Correct 273 ms 329348 KB Output is correct
3 Correct 282 ms 329348 KB Output is correct
4 Correct 278 ms 329348 KB Output is correct
5 Correct 277 ms 329408 KB Output is correct
6 Correct 278 ms 329428 KB Output is correct
7 Correct 273 ms 329428 KB Output is correct
8 Correct 269 ms 329428 KB Output is correct
9 Correct 264 ms 329428 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 329336 KB Output is correct
2 Correct 273 ms 329348 KB Output is correct
3 Correct 282 ms 329348 KB Output is correct
4 Correct 278 ms 329348 KB Output is correct
5 Correct 277 ms 329408 KB Output is correct
6 Correct 278 ms 329428 KB Output is correct
7 Correct 273 ms 329428 KB Output is correct
8 Correct 269 ms 329428 KB Output is correct
9 Correct 264 ms 329428 KB Output is correct
10 Correct 308 ms 332688 KB Output is correct
11 Correct 312 ms 332688 KB Output is correct
12 Correct 317 ms 332688 KB Output is correct
13 Correct 335 ms 333136 KB Output is correct
14 Correct 334 ms 333308 KB Output is correct
15 Correct 314 ms 333308 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4131 ms 474864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 329336 KB Output is correct
2 Correct 273 ms 329348 KB Output is correct
3 Correct 282 ms 329348 KB Output is correct
4 Correct 278 ms 329348 KB Output is correct
5 Correct 277 ms 329408 KB Output is correct
6 Correct 278 ms 329428 KB Output is correct
7 Correct 273 ms 329428 KB Output is correct
8 Correct 269 ms 329428 KB Output is correct
9 Correct 264 ms 329428 KB Output is correct
10 Correct 308 ms 332688 KB Output is correct
11 Correct 312 ms 332688 KB Output is correct
12 Correct 317 ms 332688 KB Output is correct
13 Correct 335 ms 333136 KB Output is correct
14 Correct 334 ms 333308 KB Output is correct
15 Correct 314 ms 333308 KB Output is correct
16 Execution timed out 4131 ms 474864 KB Time limit exceeded
17 Halted 0 ms 0 KB -