Submission #69340

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
69340	2018-08-20T14:33:28 Z	IvanC	Amusement Park (JOI17_amusement_park)	C++17	78 / 100	77 ms	46152 KB

#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],dfsCount;

static void dfs(int v){

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

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

}

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]);
	}	

	dfs(0);

	for(int i = 0; i < N; i++){	
		MessageBoard(i, digitos[dfs_num[i]]);
	}

}

#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];

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 dfs(int v){

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

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

}

static void find_ans(int v,int st){

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


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

	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);
	}

}

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<M;i++){
		grafo[A[i]].push_back(B[i]);
		grafo[B[i]].push_back(A[i]);
	}	

	dfs(0);

	qual_digito[P] = V;

	find_ans(P,-1);

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

	return ans;

}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	14568 KB	Output is correct
2	Correct	20 ms	27920 KB	Output is correct
3	Correct	20 ms	27984 KB	Output is correct
4	Correct	20 ms	28160 KB	Output is correct
5	Correct	24 ms	28384 KB	Output is correct
6	Correct	19 ms	28460 KB	Output is correct
7	Correct	20 ms	28536 KB	Output is correct
8	Correct	28 ms	28680 KB	Output is correct
9	Correct	24 ms	28768 KB	Output is correct
10	Correct	24 ms	28792 KB	Output is correct
11	Correct	27 ms	28824 KB	Output is correct
12	Correct	20 ms	28832 KB	Output is correct
13	Correct	24 ms	28832 KB	Output is correct
14	Correct	18 ms	28832 KB	Output is correct
15	Correct	23 ms	28856 KB	Output is correct
16	Correct	18 ms	28884 KB	Output is correct
17	Correct	19 ms	28980 KB	Output is correct
18	Correct	24 ms	29072 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	30412 KB	Output is correct
2	Correct	47 ms	31944 KB	Output is correct
3	Correct	77 ms	32380 KB	Output is correct
4	Correct	40 ms	32624 KB	Output is correct
5	Correct	37 ms	32624 KB	Output is correct
6	Correct	36 ms	32624 KB	Output is correct
7	Correct	36 ms	32624 KB	Output is correct
8	Correct	53 ms	32624 KB	Output is correct
9	Correct	47 ms	32700 KB	Output is correct
10	Correct	36 ms	32776 KB	Output is correct
11	Correct	34 ms	32776 KB	Output is correct
12	Correct	40 ms	32776 KB	Output is correct
13	Correct	38 ms	32776 KB	Output is correct
14	Correct	40 ms	32788 KB	Output is correct
15	Correct	44 ms	32976 KB	Output is correct
16	Correct	40 ms	33304 KB	Output is correct
17	Correct	37 ms	33492 KB	Output is correct
18	Correct	44 ms	33680 KB	Output is correct
19	Correct	36 ms	33932 KB	Output is correct
20	Correct	34 ms	34572 KB	Output is correct
21	Correct	33 ms	35216 KB	Output is correct
22	Correct	41 ms	35320 KB	Output is correct
23	Correct	40 ms	35320 KB	Output is correct
24	Correct	37 ms	35532 KB	Output is correct
25	Correct	39 ms	35744 KB	Output is correct
26	Correct	40 ms	35816 KB	Output is correct
27	Correct	37 ms	35984 KB	Output is correct
28	Correct	43 ms	36396 KB	Output is correct
29	Correct	36 ms	36712 KB	Output is correct
30	Correct	45 ms	36712 KB	Output is correct
31	Correct	20 ms	36712 KB	Output is correct
32	Correct	19 ms	36712 KB	Output is correct
33	Correct	19 ms	36712 KB	Output is correct
34	Correct	24 ms	36712 KB	Output is correct
35	Correct	18 ms	36712 KB	Output is correct
36	Correct	22 ms	36712 KB	Output is correct
37	Correct	18 ms	36712 KB	Output is correct
38	Correct	20 ms	36712 KB	Output is correct
39	Correct	20 ms	36712 KB	Output is correct
40	Correct	17 ms	36712 KB	Output is correct
41	Correct	19 ms	36712 KB	Output is correct
42	Correct	22 ms	36712 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	36712 KB	Output is correct
2	Correct	21 ms	36712 KB	Output is correct
3	Correct	20 ms	36712 KB	Output is correct
4	Correct	24 ms	36712 KB	Output is correct
5	Correct	24 ms	36712 KB	Output is correct
6	Correct	22 ms	36712 KB	Output is correct
7	Correct	22 ms	36712 KB	Output is correct
8	Correct	23 ms	36712 KB	Output is correct
9	Correct	36 ms	37464 KB	Output is correct
10	Correct	32 ms	38308 KB	Output is correct
11	Correct	35 ms	38460 KB	Output is correct
12	Correct	24 ms	38520 KB	Output is correct
13	Correct	20 ms	38520 KB	Output is correct
14	Correct	18 ms	38520 KB	Output is correct
15	Correct	19 ms	38520 KB	Output is correct

Subtask #4
50.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	38732 KB	Output is correct
2	Partially correct	49 ms	39140 KB	Partially correct
3	Correct	64 ms	39568 KB	Output is correct
4	Correct	43 ms	39800 KB	Output is correct
5	Correct	45 ms	39836 KB	Output is correct
6	Correct	36 ms	39872 KB	Output is correct
7	Correct	38 ms	39872 KB	Output is correct
8	Correct	36 ms	39872 KB	Output is correct
9	Correct	33 ms	39924 KB	Output is correct
10	Correct	33 ms	39976 KB	Output is correct
11	Correct	43 ms	39976 KB	Output is correct
12	Correct	33 ms	39976 KB	Output is correct
13	Correct	40 ms	39976 KB	Output is correct
14	Correct	39 ms	40144 KB	Output is correct
15	Correct	38 ms	40488 KB	Output is correct
16	Correct	37 ms	40664 KB	Output is correct
17	Correct	42 ms	40788 KB	Output is correct
18	Correct	52 ms	41004 KB	Output is correct
19	Correct	34 ms	41196 KB	Output is correct
20	Correct	34 ms	41776 KB	Output is correct
21	Correct	34 ms	42352 KB	Output is correct
22	Correct	36 ms	42448 KB	Output is correct
23	Correct	43 ms	42516 KB	Output is correct
24	Correct	42 ms	42680 KB	Output is correct
25	Correct	36 ms	42888 KB	Output is correct
26	Correct	37 ms	43080 KB	Output is correct
27	Correct	38 ms	43420 KB	Output is correct
28	Correct	40 ms	43680 KB	Output is correct
29	Correct	40 ms	43680 KB	Output is correct
30	Correct	38 ms	43944 KB	Output is correct

Subtask #5
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	44796 KB	Output is correct
2	Correct	48 ms	45576 KB	Output is correct
3	Correct	49 ms	45960 KB	Output is correct
4	Incorrect	35 ms	46152 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Submission #69340

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 50.0 / 55.0

Subtask #5 0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
50.0 / 55.0

Subtask #5
0 / 17.0