Submission #246235

#	Time	Username	Problem	Language	Result	Execution time	Memory
246235		kshitij_sodani	Amusement Park (JOI17_amusement_park)	C++14	10 / 100	239 ms	12032 KiB

Joi

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#include "Joi.h"
int par[10001];
int find(int no){
	if(par[no]==no){
		return no;
	}
	no=find(par[no]);
	return no;
}
vector<int> adj2[10001];
int par5[10001];
long long xx;
long long co=0;
vector<int> le;
vector<int> pp;
void dfs3(int no,int par2=-1){
	par5[no]=par2;
	for(auto j:adj2[no]){
		if(j==par2){
			continue;
		}
		dfs3(j,no);
	}

}
vector<int> adj3[10001];

void dfs4(int no){
	pp.pb(no);
	for(auto j:adj2[no]){
		if(j==par5[no]){
			continue;
		}
		if(pp.size()<60){
			dfs4(j);
			adj3[no].pb(j);
			adj3[j].pb(no);
		}
		else{
			le.pb(j);
		}
	}
}
vector<int> mm;
int col[10001];
vector<int> comp[10001];
void dfs5(int no,int last=-1){
	mm.pb(no);
	for(auto j:adj2[no]){
		if(j==last){
			continue;
		}
		if(mm.size()<60-pp.size()){
			dfs5(j,no);
		}
	}
}

void Joi(int n, int m, int A[], int B[], long long X, int T) {
	xx=X;
	for(int i=0;i<n;i++){
		par[i]=i;
	}
	for(int i=0;i<m;i++){
		int x=find(A[i]);
		int y=find(B[i]);
		if(x!=y){
			par[x]=y;
			adj2[A[i]].pb(B[i]);
			adj2[B[i]].pb(A[i]);
		}
	}
	dfs3(0);
	le.pb(0);
	while(le.size()){
		int x=le.back();
		le.pop_back();
		pp.clear();
		dfs4(x);
		if(pp.size()==60){
			int j=0;
			for(auto i:pp){
				col[i]=j;
				comp[i]=pp;
				j+=1;
			}
		}
		else{
			mm.clear();
			dfs5(par5[x]);
			int vis[60];
			for(int i=0;i<60;i++){
				vis[i]=0;
			}
			int ind=0;
			for(auto j:pp){
				comp[j]=pp;
			}
			for(auto j:mm){
				vis[col[j]]=1;
				for(auto kk:pp){
					comp[kk].pb(j);
				}
			}
			for(auto j:pp){
				while(vis[ind]){
					ind++;
				}
				col[j]=ind;
				ind++;
			}
		}
	}	
	/*for(int i=0;i<n;i++){
		cout<<col[i]<<":";
		for(auto j:comp[i]){
			cout<<j<<",";
		}
		cout<<endl;
	}
*/
	for(int i=0;i<n;i++){
		if((X&((llo)((llo)1<<col[i])))){
			MessageBoard(i,1);
		}
		else{
			MessageBoard(i,0);
		}
	}
}

Ioi

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#include "Joi.h"
int par7[10001];
int find9(int no){
	if(par7[no]==no){
		return no;
	}
	no=find9(par7[no]);
	return no;
}
vector<int> adj4[10001];
int par55[10001];
vector<int> le2;
vector<int> pe;
void dfs6(int no,int par2=-1){
	par55[no]=par2;
	for(auto j:adj4[no]){
		if(j==par2){
			continue;
		}
		dfs6(j,no);
	}

}
vector<int> adj5[10001];

void dfs7(int no){
	pe.pb(no);
	for(auto j:adj4[no]){
		if(j==par55[no]){
			continue;
		}
		if(pe.size()<60){
			dfs7(j);
			adj5[no].pb(j);
			adj5[j].pb(no);
		}
		else{
			le2.pb(j);
		}
	}
}
vector<int> mm2;
int col2[10001];
vector<int> comp2[10001];
vector<int> adj11[10001];

void dfs8(int no,int last=-1){
	mm2.pb(no);
	for(auto j:adj4[no]){
		if(j==last){
			continue;
		}
		if(mm2.size()<60-pe.size()){
			dfs8(j,no);
		}
	}
}

long long fin=0;
void dfs12(int no,int last=-1){
	for(auto j:adj11[no]){
		if(j==last){
			continue;
		}
		fin+=(Move(j))*((llo)1<<col2[j]);
		dfs12(j,no);
		Move(no);
	}
}
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
	for(int i=0;i<n;i++){
		par7[i]=i;
	}
	for(int i=0;i<m;i++){
		int x=find9(A[i]);
		int y=find9(B[i]);
		if(x!=y){
			par7[x]=y;
			adj4[A[i]].pb(B[i]);
			adj4[B[i]].pb(A[i]);
		}
	}
	dfs6(0);
	le2.pb(0);
	while(le2.size()){
		int x=le2.back();
		le2.pop_back();
		pe.clear();
		dfs7(x);
		if(pe.size()==60){
			int j=0;
			for(auto i:pe){
				col2[i]=j;
				comp2[i]=pe;
				j+=1;
			}
		}
		else{
			mm2.clear();
			dfs8(par55[x]);
			int vis[60];
			for(int i=0;i<60;i++){
				vis[i]=0;
			}
			int ind=0;
			for(auto j:pe){
				comp2[j]=pe;
			}
			for(auto j:mm2){
				vis[col2[j]]=1;
				for(auto kk:pe){
					comp2[kk].pb(j);
				}
			}
			for(auto j:pe){
				while(vis[ind]){
					ind++;
				}
				col2[j]=ind;
				ind++;
			}
		}
	}	
	set<int> kot;
	for(auto j:comp2[P]){
		kot.insert(j);
	}
	for(auto j:comp2[P]){
		if(kot.find(par55[j])!=kot.end()){
			adj11[j].pb(par55[j]);
			adj11[par55[j]].pb(j);
		}
	}

	
	if(V){
		fin+=((llo)1<<col2[P]);
	}
	dfs12(P);


	return fin;
}

/*
g++ -std=c++14 -O2 -o aa grader.cpp Joi.cpp Ioi.cpp
*/
/*

7 6 0 5 1
0 1
1 2
0 3
3 4
3 5
0 6





*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17