답안 #69456 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69456	2018-08-21T00:24:26 Z	IvanC	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	102 ms	34936 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) relevante[u] = 1;
 
	for(int u : copia){
		int w = pai[u];
		if(w == -1 || !relevante[w]) continue;
		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;
		relevante[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<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) relevante[u] = 1;
 
	for(int u : copia){
		int w = pai[u];
		if(w == -1 || !relevante[w]) continue;
		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;
		relevante[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;
		qual_digito[u] = Move(u);
		dfs(u);
		Move(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);
 
	return ans;
 
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	2124 KB	Output is correct
2	Correct	6 ms	2464 KB	Output is correct
3	Correct	6 ms	2860 KB	Output is correct
4	Correct	4 ms	3000 KB	Output is correct
5	Correct	5 ms	3000 KB	Output is correct
6	Correct	6 ms	3000 KB	Output is correct
7	Correct	6 ms	3148 KB	Output is correct
8	Correct	6 ms	3184 KB	Output is correct
9	Correct	8 ms	3200 KB	Output is correct
10	Correct	6 ms	3200 KB	Output is correct
11	Correct	10 ms	3200 KB	Output is correct
12	Correct	5 ms	3200 KB	Output is correct
13	Correct	7 ms	3328 KB	Output is correct
14	Correct	7 ms	3456 KB	Output is correct
15	Correct	7 ms	3460 KB	Output is correct
16	Correct	6 ms	3564 KB	Output is correct
17	Correct	6 ms	3664 KB	Output is correct
18	Correct	6 ms	3664 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	34800 KB	Output is correct
2	Correct	76 ms	34924 KB	Output is correct
3	Correct	84 ms	34936 KB	Output is correct
4	Correct	60 ms	34936 KB	Output is correct
5	Correct	57 ms	34936 KB	Output is correct
6	Correct	60 ms	34936 KB	Output is correct
7	Correct	61 ms	34936 KB	Output is correct
8	Correct	64 ms	34936 KB	Output is correct
9	Correct	73 ms	34936 KB	Output is correct
10	Correct	62 ms	34936 KB	Output is correct
11	Correct	71 ms	34936 KB	Output is correct
12	Correct	65 ms	34936 KB	Output is correct
13	Correct	64 ms	34936 KB	Output is correct
14	Correct	62 ms	34936 KB	Output is correct
15	Correct	59 ms	34936 KB	Output is correct
16	Correct	61 ms	34936 KB	Output is correct
17	Correct	61 ms	34936 KB	Output is correct
18	Correct	70 ms	34936 KB	Output is correct
19	Correct	60 ms	34936 KB	Output is correct
20	Correct	59 ms	34936 KB	Output is correct
21	Correct	55 ms	34936 KB	Output is correct
22	Correct	72 ms	34936 KB	Output is correct
23	Correct	67 ms	34936 KB	Output is correct
24	Correct	59 ms	34936 KB	Output is correct
25	Correct	57 ms	34936 KB	Output is correct
26	Correct	59 ms	34936 KB	Output is correct
27	Correct	66 ms	34936 KB	Output is correct
28	Correct	61 ms	34936 KB	Output is correct
29	Correct	69 ms	34936 KB	Output is correct
30	Correct	55 ms	34936 KB	Output is correct
31	Correct	6 ms	34936 KB	Output is correct
32	Correct	6 ms	34936 KB	Output is correct
33	Correct	6 ms	34936 KB	Output is correct
34	Correct	6 ms	34936 KB	Output is correct
35	Correct	6 ms	34936 KB	Output is correct
36	Correct	6 ms	34936 KB	Output is correct
37	Correct	7 ms	34936 KB	Output is correct
38	Correct	8 ms	34936 KB	Output is correct
39	Correct	6 ms	34936 KB	Output is correct
40	Correct	7 ms	34936 KB	Output is correct
41	Correct	6 ms	34936 KB	Output is correct
42	Correct	5 ms	34936 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	34936 KB	Output is correct
2	Correct	6 ms	34936 KB	Output is correct
3	Correct	7 ms	34936 KB	Output is correct
4	Correct	13 ms	34936 KB	Output is correct
5	Correct	13 ms	34936 KB	Output is correct
6	Correct	12 ms	34936 KB	Output is correct
7	Correct	13 ms	34936 KB	Output is correct
8	Correct	12 ms	34936 KB	Output is correct
9	Correct	79 ms	34936 KB	Output is correct
10	Correct	56 ms	34936 KB	Output is correct
11	Correct	54 ms	34936 KB	Output is correct
12	Correct	6 ms	34936 KB	Output is correct
13	Correct	4 ms	34936 KB	Output is correct
14	Correct	5 ms	34936 KB	Output is correct
15	Correct	5 ms	34936 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	34936 KB	Output is correct
2	Correct	87 ms	34936 KB	Output is correct
3	Correct	102 ms	34936 KB	Output is correct
4	Correct	81 ms	34936 KB	Output is correct
5	Correct	73 ms	34936 KB	Output is correct
6	Correct	70 ms	34936 KB	Output is correct
7	Correct	62 ms	34936 KB	Output is correct
8	Correct	68 ms	34936 KB	Output is correct
9	Correct	72 ms	34936 KB	Output is correct
10	Correct	75 ms	34936 KB	Output is correct
11	Correct	63 ms	34936 KB	Output is correct
12	Correct	70 ms	34936 KB	Output is correct
13	Correct	72 ms	34936 KB	Output is correct
14	Correct	68 ms	34936 KB	Output is correct
15	Correct	75 ms	34936 KB	Output is correct
16	Correct	64 ms	34936 KB	Output is correct
17	Correct	74 ms	34936 KB	Output is correct
18	Correct	72 ms	34936 KB	Output is correct
19	Correct	74 ms	34936 KB	Output is correct
20	Correct	64 ms	34936 KB	Output is correct
21	Correct	57 ms	34936 KB	Output is correct
22	Correct	65 ms	34936 KB	Output is correct
23	Correct	76 ms	34936 KB	Output is correct
24	Correct	76 ms	34936 KB	Output is correct
25	Correct	69 ms	34936 KB	Output is correct
26	Correct	68 ms	34936 KB	Output is correct
27	Correct	76 ms	34936 KB	Output is correct
28	Correct	61 ms	34936 KB	Output is correct
29	Correct	62 ms	34936 KB	Output is correct
30	Correct	62 ms	34936 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	85 ms	34936 KB	Output is correct
2	Correct	89 ms	34936 KB	Output is correct
3	Correct	94 ms	34936 KB	Output is correct
4	Correct	68 ms	34936 KB	Output is correct
5	Correct	65 ms	34936 KB	Output is correct
6	Correct	62 ms	34936 KB	Output is correct
7	Correct	62 ms	34936 KB	Output is correct
8	Correct	63 ms	34936 KB	Output is correct
9	Correct	66 ms	34936 KB	Output is correct
10	Correct	65 ms	34936 KB	Output is correct
11	Correct	73 ms	34936 KB	Output is correct
12	Correct	71 ms	34936 KB	Output is correct
13	Correct	65 ms	34936 KB	Output is correct
14	Correct	63 ms	34936 KB	Output is correct
15	Correct	65 ms	34936 KB	Output is correct
16	Correct	64 ms	34936 KB	Output is correct
17	Correct	57 ms	34936 KB	Output is correct
18	Correct	59 ms	34936 KB	Output is correct
19	Correct	60 ms	34936 KB	Output is correct
20	Correct	51 ms	34936 KB	Output is correct
21	Correct	52 ms	34936 KB	Output is correct
22	Correct	69 ms	34936 KB	Output is correct
23	Correct	66 ms	34936 KB	Output is correct
24	Correct	57 ms	34936 KB	Output is correct
25	Correct	57 ms	34936 KB	Output is correct
26	Correct	58 ms	34936 KB	Output is correct
27	Correct	58 ms	34936 KB	Output is correct
28	Correct	64 ms	34936 KB	Output is correct
29	Correct	57 ms	34936 KB	Output is correct
30	Correct	67 ms	34936 KB	Output is correct
31	Correct	6 ms	34936 KB	Output is correct
32	Correct	6 ms	34936 KB	Output is correct
33	Correct	8 ms	34936 KB	Output is correct
34	Correct	6 ms	34936 KB	Output is correct
35	Correct	6 ms	34936 KB	Output is correct
36	Correct	5 ms	34936 KB	Output is correct
37	Correct	4 ms	34936 KB	Output is correct
38	Correct	5 ms	34936 KB	Output is correct
39	Correct	6 ms	34936 KB	Output is correct
40	Correct	5 ms	34936 KB	Output is correct
41	Correct	5 ms	34936 KB	Output is correct
42	Correct	5 ms	34936 KB	Output is correct

답안 #69456

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