답안 #69455 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69455	2018-08-21T00:22:33 Z	IvanC	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	328 ms	43040 KB

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

const int MAXN = 10011;
const int MAXL = 60;

static vector<int> grafo[MAXN],tree[MAXN],lista;
static bitset<MAXN> adjMat[MAXN];
static int digito[MAXL],pai[MAXN],contador[MAXN],idx[MAXN],relevante[MAXN];

static void bfs(){

	memset(contador,0,sizeof(contador));
	pai[0] = -1;
	contador[0] = 1;
	queue<int> fila;
	fila.push(0);

	while(!fila.empty()){
		int v = fila.front();
		fila.pop();
		lista.push_back(v);
		for(int u : grafo[v]){
			if(contador[u]) continue;
			contador[u] = 1;
			pai[u] = v;
			fila.push(u);
			adjMat[v][u] = 1;
			adjMat[u][v] = 1;
		}
	}

	memset(contador,0,sizeof(contador));

}

static void build_first(){

	vector<int> primeiro;
	for(int i = 0;i<MAXL;i++){
		primeiro.push_back(lista[i]);
		idx[primeiro.back()] = i;
	}

	for(int i : primeiro) tree[i] = primeiro;

}

static void extend_tree(int v){

	vector<int> copia = tree[pai[v]];

	for(int u : copia){
		for(int w : copia){
			if(adjMat[u][w] && u < w){
				contador[u]++;
				contador[w]++;
			}
		}
	}

	int achei = -1;

	for(int u : copia){
		if(u == pai[v]) continue;
		if(contador[u] == 1){
			achei = u;
			break;
		}
	}

	for(int u : copia){
		contador[u] = 0;
		if(u != achei) tree[v].push_back(u);
	}

	tree[v].push_back(v);
	idx[v] = idx[achei];

}

void Joi(int N, int M, int A[], int B[], long long X, int T){
	
	for(int i = 0;i<MAXL;i++){
		if(X & (1LL << i)) digito[i] = 1;
		else digito[i] = 0;
	}

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

	bfs();
	build_first();
	for(int i = MAXL;i<N;i++) extend_tree(lista[i]);

	//for(int i = 0;i<MAXL;i++) printf("%d",digito[i]);
	//printf("\n");

	for(int i = 0;i<N;i++) MessageBoard(i, digito[idx[i]] );

}

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

const int MAXN = 10011;
const int MAXL = 60;

static vector<int> grafo[MAXN],tree[MAXN],lista;
static bitset<MAXN> adjMat[MAXN];
static int digito[MAXL],pai[MAXN],contador[MAXN],idx[MAXN],qual_digito[MAXN],relevante[MAXN];

static void bfs(){

	memset(contador,0,sizeof(contador));
	pai[0] = -1;
	contador[0] = 1;
	queue<int> fila;
	fila.push(0);

	while(!fila.empty()){
		int v = fila.front();
		fila.pop();
		lista.push_back(v);
		for(int u : grafo[v]){
			if(contador[u]) continue;
			contador[u] = 1;
			pai[u] = v;
			fila.push(u);
			adjMat[v][u] = 1;
			adjMat[u][v] = 1;
		}
	}

	memset(contador,0,sizeof(contador));

}

static void build_first(){

	vector<int> primeiro;
	for(int i = 0;i<MAXL;i++){
		primeiro.push_back(lista[i]);
		idx[primeiro.back()] = i;
	}

	for(int i : primeiro) tree[i] = primeiro;

}

static void extend_tree(int v){

	vector<int> copia = tree[pai[v]];

	for(int u : copia){
		for(int w : copia){
			if(adjMat[u][w] && u < w){
				contador[u]++;
				contador[w]++;
			}
		}
	}

	int achei = -1;

	for(int u : copia){
		if(u == pai[v]) continue;
		if(contador[u] == 1){
			achei = u;
			break;
		}
	}

	for(int u : copia){
		contador[u] = 0;
		if(u != achei) tree[v].push_back(u);
	}

	tree[v].push_back(v);
	idx[v] = idx[achei];

}

static void dfs(int v){

	contador[v] = 1;
	digito[idx[v]] = qual_digito[v];

	for(int u : grafo[v]){
		if(!adjMat[u][v] || contador[u] || !relevante[u]) continue;
		//printf("V %d -> U %d\n",v,u);
		qual_digito[u] = Move(u);
		dfs(u);
		Move(v);
		//printf("U %d -> V %d\n",u,v);
	}

}

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

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

	bfs();
	build_first();
	for(int i = MAXL;i<N;i++) extend_tree(lista[i]);

	memset(relevante,0,sizeof(relevante));
	for(int i : tree[P]) relevante[i] = 1;
	qual_digito[P] = V;
	dfs(P);

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

	//for(int i = 0;i<MAXL;i++) printf("%d",((1LL << i) & ans) != 0);
	//printf("\n");

	return ans;

}

Compilation message

Joi.cpp:10:60: warning: 'relevante' defined but not used [-Wunused-variable]
 static int digito[MAXL],pai[MAXN],contador[MAXN],idx[MAXN],relevante[MAXN];
                                                            ^~~~~~~~~

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	1896 KB	Output is correct
2	Correct	9 ms	2392 KB	Output is correct
3	Correct	15 ms	2872 KB	Output is correct
4	Correct	8 ms	3000 KB	Output is correct
5	Correct	7 ms	3000 KB	Output is correct
6	Correct	9 ms	3000 KB	Output is correct
7	Correct	10 ms	3228 KB	Output is correct
8	Correct	10 ms	3300 KB	Output is correct
9	Correct	10 ms	3304 KB	Output is correct
10	Correct	8 ms	3304 KB	Output is correct
11	Correct	13 ms	3304 KB	Output is correct
12	Correct	7 ms	3304 KB	Output is correct
13	Correct	11 ms	3464 KB	Output is correct
14	Correct	11 ms	3620 KB	Output is correct
15	Correct	13 ms	3632 KB	Output is correct
16	Correct	10 ms	3640 KB	Output is correct
17	Correct	12 ms	3644 KB	Output is correct
18	Correct	14 ms	3652 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	250 ms	35252 KB	Output is correct
2	Correct	284 ms	35652 KB	Output is correct
3	Correct	258 ms	36036 KB	Output is correct
4	Correct	264 ms	36168 KB	Output is correct
5	Correct	273 ms	36168 KB	Output is correct
6	Correct	290 ms	36168 KB	Output is correct
7	Correct	265 ms	36168 KB	Output is correct
8	Correct	265 ms	36376 KB	Output is correct
9	Correct	296 ms	36504 KB	Output is correct
10	Correct	232 ms	37104 KB	Output is correct
11	Correct	277 ms	37104 KB	Output is correct
12	Correct	276 ms	37104 KB	Output is correct
13	Correct	220 ms	37104 KB	Output is correct
14	Correct	275 ms	37104 KB	Output is correct
15	Correct	306 ms	37536 KB	Output is correct
16	Correct	263 ms	37624 KB	Output is correct
17	Correct	269 ms	37692 KB	Output is correct
18	Correct	247 ms	37760 KB	Output is correct
19	Correct	258 ms	37884 KB	Output is correct
20	Correct	205 ms	38008 KB	Output is correct
21	Correct	221 ms	38008 KB	Output is correct
22	Correct	236 ms	38008 KB	Output is correct
23	Correct	236 ms	38008 KB	Output is correct
24	Correct	255 ms	38008 KB	Output is correct
25	Correct	242 ms	38008 KB	Output is correct
26	Correct	264 ms	38008 KB	Output is correct
27	Correct	246 ms	38008 KB	Output is correct
28	Correct	232 ms	38008 KB	Output is correct
29	Correct	224 ms	38008 KB	Output is correct
30	Correct	228 ms	38008 KB	Output is correct
31	Correct	9 ms	38008 KB	Output is correct
32	Correct	8 ms	38008 KB	Output is correct
33	Correct	9 ms	38008 KB	Output is correct
34	Correct	8 ms	38008 KB	Output is correct
35	Correct	6 ms	38008 KB	Output is correct
36	Correct	6 ms	38008 KB	Output is correct
37	Correct	6 ms	38008 KB	Output is correct
38	Correct	6 ms	38008 KB	Output is correct
39	Correct	6 ms	38008 KB	Output is correct
40	Correct	8 ms	38008 KB	Output is correct
41	Correct	8 ms	38008 KB	Output is correct
42	Correct	7 ms	38008 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	38008 KB	Output is correct
2	Correct	7 ms	38008 KB	Output is correct
3	Correct	9 ms	38008 KB	Output is correct
4	Correct	38 ms	38008 KB	Output is correct
5	Correct	38 ms	38008 KB	Output is correct
6	Correct	38 ms	38008 KB	Output is correct
7	Correct	37 ms	38008 KB	Output is correct
8	Correct	37 ms	38008 KB	Output is correct
9	Correct	208 ms	38008 KB	Output is correct
10	Correct	221 ms	38008 KB	Output is correct
11	Correct	201 ms	38008 KB	Output is correct
12	Correct	7 ms	38008 KB	Output is correct
13	Correct	7 ms	38008 KB	Output is correct
14	Correct	7 ms	38008 KB	Output is correct
15	Correct	6 ms	38008 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	243 ms	38380 KB	Output is correct
2	Correct	253 ms	38480 KB	Output is correct
3	Correct	255 ms	38512 KB	Output is correct
4	Correct	242 ms	38512 KB	Output is correct
5	Correct	246 ms	38512 KB	Output is correct
6	Correct	232 ms	38512 KB	Output is correct
7	Correct	242 ms	38512 KB	Output is correct
8	Correct	232 ms	38512 KB	Output is correct
9	Correct	249 ms	38512 KB	Output is correct
10	Correct	204 ms	38512 KB	Output is correct
11	Correct	254 ms	38512 KB	Output is correct
12	Correct	230 ms	38512 KB	Output is correct
13	Correct	258 ms	38512 KB	Output is correct
14	Correct	268 ms	38512 KB	Output is correct
15	Correct	276 ms	38512 KB	Output is correct
16	Correct	235 ms	38512 KB	Output is correct
17	Correct	234 ms	38680 KB	Output is correct
18	Correct	236 ms	38920 KB	Output is correct
19	Correct	232 ms	38952 KB	Output is correct
20	Correct	203 ms	39092 KB	Output is correct
21	Correct	223 ms	39168 KB	Output is correct
22	Correct	267 ms	39440 KB	Output is correct
23	Correct	263 ms	39776 KB	Output is correct
24	Correct	283 ms	40000 KB	Output is correct
25	Correct	264 ms	40048 KB	Output is correct
26	Correct	307 ms	40296 KB	Output is correct
27	Correct	237 ms	40508 KB	Output is correct
28	Correct	308 ms	40576 KB	Output is correct
29	Correct	271 ms	40576 KB	Output is correct
30	Correct	285 ms	40576 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	255 ms	42264 KB	Output is correct
2	Correct	262 ms	42492 KB	Output is correct
3	Correct	261 ms	42888 KB	Output is correct
4	Correct	265 ms	43040 KB	Output is correct
5	Correct	254 ms	43040 KB	Output is correct
6	Correct	267 ms	43040 KB	Output is correct
7	Correct	261 ms	43040 KB	Output is correct
8	Correct	240 ms	43040 KB	Output is correct
9	Correct	298 ms	43040 KB	Output is correct
10	Correct	223 ms	43040 KB	Output is correct
11	Correct	209 ms	43040 KB	Output is correct
12	Correct	252 ms	43040 KB	Output is correct
13	Correct	224 ms	43040 KB	Output is correct
14	Correct	256 ms	43040 KB	Output is correct
15	Correct	302 ms	43040 KB	Output is correct
16	Correct	299 ms	43040 KB	Output is correct
17	Correct	242 ms	43040 KB	Output is correct
18	Correct	328 ms	43040 KB	Output is correct
19	Correct	296 ms	43040 KB	Output is correct
20	Correct	231 ms	43040 KB	Output is correct
21	Correct	223 ms	43040 KB	Output is correct
22	Correct	273 ms	43040 KB	Output is correct
23	Correct	298 ms	43040 KB	Output is correct
24	Correct	305 ms	43040 KB	Output is correct
25	Correct	294 ms	43040 KB	Output is correct
26	Correct	327 ms	43040 KB	Output is correct
27	Correct	268 ms	43040 KB	Output is correct
28	Correct	273 ms	43040 KB	Output is correct
29	Correct	229 ms	43040 KB	Output is correct
30	Correct	250 ms	43040 KB	Output is correct
31	Correct	8 ms	43040 KB	Output is correct
32	Correct	8 ms	43040 KB	Output is correct
33	Correct	11 ms	43040 KB	Output is correct
34	Correct	8 ms	43040 KB	Output is correct
35	Correct	8 ms	43040 KB	Output is correct
36	Correct	6 ms	43040 KB	Output is correct
37	Correct	7 ms	43040 KB	Output is correct
38	Correct	6 ms	43040 KB	Output is correct
39	Correct	5 ms	43040 KB	Output is correct
40	Correct	6 ms	43040 KB	Output is correct
41	Correct	6 ms	43040 KB	Output is correct
42	Correct	6 ms	43040 KB	Output is correct

답안 #69455

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 55.0 / 55.0

Subtask #5 17.0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
55.0 / 55.0

Subtask #5
17.0 / 17.0