Submission #69402

#	Time	Username	Problem	Language	Result	Execution time	Memory
69402		IvanC	Amusement Park (JOI17_amusement_park)	C++17	81 / 100	68 ms	31832 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10011;
const int MOD = 60;

static vector<int> grafo[MAXN],digitos;
static int dfs_num[MAXN],nivel[MAXN],dfsCount,maior[MAXN],valor[MAXN];

static void dfs(int v){

	dfs_num[v] = dfsCount % MOD;
	dfsCount++;

	for(int u : grafo[v]){
		if(dfs_num[u] != -1) continue;
		nivel[u] = nivel[v] + 1;
		dfs(u);
		maior[v] = max(maior[v],maior[u]);
	}

}

static bool compara(int a,int b){
	return valor[a] < valor[b];
}

void Joi(int N, int M, int A[], int B[], long long X, int T){
	
	memset(dfs_num,-1,sizeof(dfs_num));
	dfsCount = 0;
	for(int i = 0;i<N;i++) grafo[i].clear();
	digitos.clear();

	for(int i = 0;i<MOD;i++){
		if((1LL << i) & X)	digitos.push_back(1);
		else digitos.push_back(0);
	}

	for(int i = 0;i<M;i++){
		grafo[A[i]].push_back(B[i]);
		grafo[B[i]].push_back(A[i]);
	}	

	knuth_b gen2(999999599);
	for(int i = 0;i<N;i++) valor[i] = gen2();

	for(int i = 0;i<N;i++) sort(grafo[i].begin(),grafo[i].end(),compara);

	dfs(0);

	if(maior[0] + 1 < MOD){
		for(int i = 0; i < N; i++){	
			MessageBoard(i, digitos[dfs_num[i]]);
		}
	}
	else{
		for(int i = 0;i<N;i++) MessageBoard(i, digitos[nivel[i] % MOD] );
	}

}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10011;
const int MOD = 60;

static deque<int> grafo[MAXN],tree[MAXN];
static int digitos[MOD],freq[MOD],distintos,processado[MAXN],dfsCount,dfs_num[MAXN],qual_digito[MAXN],pai[MAXN],nivel[MAXN],maior[MAXN],valor[MAXN];

static void add_number(int x){
	if(freq[x] == 0) distintos++;
	freq[x]++;
}

static void add_vertex(int v){
	digitos[dfs_num[v]] = qual_digito[v];
	add_number(dfs_num[v]);
}

static void greedy_add(int v){
	int qual = nivel[v] % MOD;
	digitos[qual] = qual_digito[v];
	add_number(qual);
}

static void dfs(int v){

	dfs_num[v] = dfsCount % MOD;
	dfsCount++;

	for(int u : grafo[v]){
		if(dfs_num[u] != -1) continue;
		pai[u] = v;
		nivel[u] = nivel[v] + 1;
		tree[v].push_back(u);
		dfs(u);
		maior[v] = max(maior[v],maior[u]);
	}

}

static void find_ans(int v,int st){

	processado[v] = 1;
	add_vertex(v);
	if(distintos == MOD) return;

	deque<int> temp;

	while(st != -1 && tree[v].front() != st){
		temp.push_front(tree[v].front());
		tree[v].pop_front();
	}

	for(int u : temp) tree[v].push_back(u);
	temp.clear();

	for(int u : tree[v]){
		if(distintos == MOD) return;
		if(processado[u]) continue;
		int davez = Move(u);
		qual_digito[u] = davez;
		find_ans(u,-1);
		if(distintos == MOD) return;
		Move(v);
	}

	if(distintos != MOD){
		int davez = Move(pai[v]);
		qual_digito[pai[v]] = davez;
		find_ans(pai[v],v);
	}

}

static void greedy(int v){

	greedy_add(v);
	while(v != 0 && distintos != MOD){
		int u = pai[v];
		qual_digito[u] = Move(u);
		greedy_add(u);
		v = u;
	}

	if(distintos == MOD) return;

	while(distintos != MOD){
		int mx = -1,alvo = -1;
		for(int u : tree[v]){
			if(maior[u] > mx){
				mx = maior[u];
				alvo = u;
			}
		}
		qual_digito[alvo] = Move(alvo);
		greedy_add(alvo);
		v = alvo;
	}

}

static bool compara(int a,int b){
	return valor[a] < valor[b];
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {

	memset(dfs_num,-1,sizeof(dfs_num));
	memset(processado,0,sizeof(processado));
	memset(freq,0,sizeof(freq));
	dfsCount = 0;
	distintos = 0;
	for(int i = 0;i<N;i++) grafo[i].clear();
	for(int i = 0;i<N;i++) tree[i].clear();

	for(int i = 0;i<M;i++){
		grafo[A[i]].push_back(B[i]);
		grafo[B[i]].push_back(A[i]);
	}	

	knuth_b gen1(999999599);
	for(int i = 0;i<N;i++) valor[i] = gen1();

	for(int i = 0;i<N;i++) sort(grafo[i].begin(),grafo[i].end(),compara);

	dfs(0);

	qual_digito[P] = V;

	if(maior[0] + 1 < MOD) find_ans(P,-1);
	else greedy(P);

	long long ans = 0;
	for(int i = 0;i<MOD;i++) if(digitos[i]) ans += (1LL << i);

	return ans;

}

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