oj.uz

Submission #84823

# Submission time Handle Problem Language Result Execution time Memory
84823 2018-11-17T11:01:18 Z KLPP Werewolf (IOI18_werewolf) C++14
49 / 100
 1512 ms 525312 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 333112 KB Output is correct
2 Correct 273 ms 333148 KB Output is correct
3 Correct 276 ms 333148 KB Output is correct
4 Correct 277 ms 333308 KB Output is correct
5 Correct 277 ms 333336 KB Output is correct
6 Correct 277 ms 333336 KB Output is correct
7 Correct 278 ms 333364 KB Output is correct
8 Correct 283 ms 333364 KB Output is correct
9 Correct 290 ms 333444 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 333112 KB Output is correct
2 Correct 273 ms 333148 KB Output is correct
3 Correct 276 ms 333148 KB Output is correct
4 Correct 277 ms 333308 KB Output is correct
5 Correct 277 ms 333336 KB Output is correct
6 Correct 277 ms 333336 KB Output is correct
7 Correct 278 ms 333364 KB Output is correct
8 Correct 283 ms 333364 KB Output is correct
9 Correct 290 ms 333444 KB Output is correct
10 Correct 282 ms 334160 KB Output is correct
11 Correct 294 ms 334224 KB Output is correct
12 Correct 288 ms 334224 KB Output is correct
13 Correct 287 ms 334240 KB Output is correct
14 Correct 297 ms 334296 KB Output is correct
15 Correct 297 ms 334404 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1249 ms 373944 KB Output is correct
2 Correct 1321 ms 383644 KB Output is correct
3 Correct 1262 ms 391220 KB Output is correct
4 Correct 1217 ms 399464 KB Output is correct
5 Correct 1184 ms 407768 KB Output is correct
6 Correct 1170 ms 416112 KB Output is correct
7 Correct 1155 ms 418140 KB Output is correct
8 Correct 1185 ms 419076 KB Output is correct
9 Correct 1020 ms 422048 KB Output is correct
10 Correct 1008 ms 430108 KB Output is correct
11 Correct 1038 ms 438416 KB Output is correct
12 Correct 1049 ms 447136 KB Output is correct
13 Correct 1505 ms 460656 KB Output is correct
14 Correct 1456 ms 469040 KB Output is correct
15 Correct 1512 ms 477640 KB Output is correct
16 Correct 1507 ms 485804 KB Output is correct
17 Correct 1162 ms 489012 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 333112 KB Output is correct
2 Correct 273 ms 333148 KB Output is correct
3 Correct 276 ms 333148 KB Output is correct
4 Correct 277 ms 333308 KB Output is correct
5 Correct 277 ms 333336 KB Output is correct
6 Correct 277 ms 333336 KB Output is correct
7 Correct 278 ms 333364 KB Output is correct
8 Correct 283 ms 333364 KB Output is correct
9 Correct 290 ms 333444 KB Output is correct
10 Correct 282 ms 334160 KB Output is correct
11 Correct 294 ms 334224 KB Output is correct
12 Correct 288 ms 334224 KB Output is correct
13 Correct 287 ms 334240 KB Output is correct
14 Correct 297 ms 334296 KB Output is correct
15 Correct 297 ms 334404 KB Output is correct
16 Correct 1249 ms 373944 KB Output is correct
17 Correct 1321 ms 383644 KB Output is correct
18 Correct 1262 ms 391220 KB Output is correct
19 Correct 1217 ms 399464 KB Output is correct
20 Correct 1184 ms 407768 KB Output is correct
21 Correct 1170 ms 416112 KB Output is correct
22 Correct 1155 ms 418140 KB Output is correct
23 Correct 1185 ms 419076 KB Output is correct
24 Correct 1020 ms 422048 KB Output is correct
25 Correct 1008 ms 430108 KB Output is correct
26 Correct 1038 ms 438416 KB Output is correct
27 Correct 1049 ms 447136 KB Output is correct
28 Correct 1505 ms 460656 KB Output is correct
29 Correct 1456 ms 469040 KB Output is correct
30 Correct 1512 ms 477640 KB Output is correct
31 Correct 1507 ms 485804 KB Output is correct
32 Correct 1162 ms 489012 KB Output is correct
33 Correct 1272 ms 497324 KB Output is correct
34 Correct 925 ms 506036 KB Output is correct
35 Correct 1376 ms 519064 KB Output is correct
36 Runtime error 1239 ms 525312 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
37 Halted 0 ms 0 KB -