답안 #394519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394519	2021-04-26T18:36:25 Z	jsannemo	Amusement Park (JOI17_amusement_park)	C++14	63 / 100	34 ms	5524 KB

#include "Joi.h"

#include <vector>
#include <map>

using namespace std;

static vector<vector<int>> adj;

static vector<int> ord;
static map<int, int> bit;
static vector<bool> seen;

static void dfs(int at) {
	seen[at] = true;
	ord.push_back(at);
	for (int it : adj[at]) {
		if (seen[it]) continue;
		dfs(it);
		ord.push_back(at);
	}
	int b = (int)bit.size();
	bit[at] = b % 60;
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	adj.resize(N);
	seen.resize(N);
	for (int i = 0; i < M; i ++) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(0);
	ord.pop_back();

  for(int i = 0; i < N; i++){
    MessageBoard(i, (X >> bit[i]) & 1);
  }
}

#include "Ioi.h"

#include <vector>
#include <map>
#include <algorithm>
#include <iostream>

using namespace std;

static vector<vector<int>> adj;

static vector<int> ord;
static map<int, int> bit;
static vector<bool> seen;
static map<int, int> bits;
static vector<int> par;

static void dfs(int at) {
	seen[at] = true;
	ord.push_back(at);
	for (int it : adj[at]) {
		if (seen[it]) continue;
		par[it] = at;
		dfs(it);
		ord.push_back(at);
	}
	int b = (int)bit.size();
	bit[at] = b % 60;
}

static void dfs2(int at) {
	for (int it : adj[at]) {
		if (bits.count(bit[it]) || it == par[at]) continue;
		bits[bit[it]] = Move(it);
		dfs2(it);
		Move(at);
	}
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	adj.resize(N);
	seen.resize(N);
	par.resize(N);
	for (int i = 0; i < M; i ++) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(0);
	ord.pop_back();

	bits[bit[P]] = V;
	while (bits.size() != 60) {
		dfs2(P);
		P = par[P];
		if (bits.size() != 60) bits[bit[P]] = Move(P);
	}
	cerr << "bits: " << bits.size() << endl;

	//int at = find(ord.begin(), ord.end(), P) - ord.begin();
	//while ((int)bits.size() != 60) {
		//at = (at + 1) % ord.size();
		//cerr << "go to " << ord[at] << " get bit " << bit[ord[at]] << endl;
		//bits[bit[ord[at]]] = Move(ord[at]);
	//}
	long long X = 0;
	for (int i = 0; i < 60; ++i) {
		X |= (long long)bits[i] << i;
	}
	return X;
}

Subtask #1
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	496 KB	Output is correct
2	Correct	2 ms	616 KB	Output is correct
3	Correct	2 ms	716 KB	Output is correct
4	Correct	2 ms	624 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	756 KB	Output is correct
8	Correct	2 ms	752 KB	Output is correct
9	Correct	2 ms	756 KB	Output is correct
10	Incorrect	2 ms	620 KB	Wrong Answer [7]
11	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	5432 KB	Output is correct
2	Correct	33 ms	5444 KB	Output is correct
3	Correct	32 ms	5388 KB	Output is correct
4	Correct	20 ms	3640 KB	Output is correct
5	Correct	23 ms	4392 KB	Output is correct
6	Correct	23 ms	4212 KB	Output is correct
7	Correct	22 ms	4296 KB	Output is correct
8	Correct	20 ms	4612 KB	Output is correct
9	Correct	22 ms	4740 KB	Output is correct
10	Correct	23 ms	3868 KB	Output is correct
11	Correct	22 ms	3936 KB	Output is correct
12	Correct	19 ms	3584 KB	Output is correct
13	Correct	19 ms	3568 KB	Output is correct
14	Correct	19 ms	3576 KB	Output is correct
15	Correct	22 ms	3796 KB	Output is correct
16	Correct	22 ms	4004 KB	Output is correct
17	Correct	22 ms	3780 KB	Output is correct
18	Correct	20 ms	3892 KB	Output is correct
19	Correct	20 ms	3800 KB	Output is correct
20	Correct	17 ms	4752 KB	Output is correct
21	Correct	16 ms	4664 KB	Output is correct
22	Correct	20 ms	4372 KB	Output is correct
23	Correct	22 ms	4572 KB	Output is correct
24	Correct	23 ms	4340 KB	Output is correct
25	Correct	22 ms	4400 KB	Output is correct
26	Correct	22 ms	4564 KB	Output is correct
27	Correct	20 ms	4648 KB	Output is correct
28	Correct	22 ms	4604 KB	Output is correct
29	Correct	19 ms	4100 KB	Output is correct
30	Correct	19 ms	4364 KB	Output is correct
31	Correct	2 ms	620 KB	Output is correct
32	Correct	2 ms	628 KB	Output is correct
33	Correct	2 ms	760 KB	Output is correct
34	Correct	2 ms	620 KB	Output is correct
35	Correct	2 ms	620 KB	Output is correct
36	Correct	2 ms	616 KB	Output is correct
37	Correct	2 ms	492 KB	Output is correct
38	Correct	2 ms	620 KB	Output is correct
39	Correct	2 ms	500 KB	Output is correct
40	Incorrect	1 ms	620 KB	Wrong Answer [7]
41	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	616 KB	Output is correct
2	Correct	2 ms	616 KB	Output is correct
3	Correct	2 ms	624 KB	Output is correct
4	Correct	4 ms	1288 KB	Output is correct
5	Correct	4 ms	1296 KB	Output is correct
6	Correct	4 ms	1284 KB	Output is correct
7	Correct	4 ms	1284 KB	Output is correct
8	Correct	4 ms	1292 KB	Output is correct
9	Correct	17 ms	5452 KB	Output is correct
10	Correct	17 ms	5444 KB	Output is correct
11	Correct	18 ms	5432 KB	Output is correct
12	Correct	1 ms	616 KB	Output is correct
13	Correct	2 ms	612 KB	Output is correct
14	Correct	1 ms	488 KB	Output is correct
15	Correct	1 ms	628 KB	Output is correct

Subtask #4
53.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	32 ms	5488 KB	Partially correct
2	Correct	32 ms	5524 KB	Output is correct
3	Correct	32 ms	5368 KB	Output is correct
4	Correct	20 ms	3652 KB	Output is correct
5	Correct	22 ms	4936 KB	Output is correct
6	Correct	22 ms	4348 KB	Output is correct
7	Correct	22 ms	4620 KB	Output is correct
8	Correct	22 ms	4124 KB	Output is correct
9	Correct	24 ms	4360 KB	Output is correct
10	Correct	22 ms	3860 KB	Output is correct
11	Correct	20 ms	3904 KB	Output is correct
12	Correct	19 ms	3572 KB	Output is correct
13	Partially correct	19 ms	3564 KB	Partially correct
14	Correct	19 ms	3656 KB	Output is correct
15	Correct	20 ms	3668 KB	Output is correct
16	Correct	20 ms	3844 KB	Output is correct
17	Correct	25 ms	3984 KB	Output is correct
18	Correct	24 ms	3880 KB	Output is correct
19	Correct	22 ms	3864 KB	Output is correct
20	Correct	17 ms	4852 KB	Output is correct
21	Correct	16 ms	4640 KB	Output is correct
22	Correct	23 ms	4624 KB	Output is correct
23	Correct	20 ms	4468 KB	Output is correct
24	Correct	22 ms	4416 KB	Output is correct
25	Correct	22 ms	4548 KB	Output is correct
26	Correct	22 ms	4492 KB	Output is correct
27	Correct	22 ms	4612 KB	Output is correct
28	Correct	22 ms	4376 KB	Output is correct
29	Correct	19 ms	4100 KB	Output is correct
30	Correct	19 ms	4368 KB	Output is correct

Subtask #5
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	5448 KB	Output is correct
2	Correct	32 ms	5356 KB	Output is correct
3	Correct	34 ms	5420 KB	Output is correct
4	Correct	22 ms	3632 KB	Output is correct
5	Correct	22 ms	5380 KB	Output is correct
6	Correct	27 ms	4224 KB	Output is correct
7	Correct	22 ms	4356 KB	Output is correct
8	Correct	22 ms	4756 KB	Output is correct
9	Correct	20 ms	4396 KB	Output is correct
10	Correct	20 ms	3836 KB	Output is correct
11	Correct	22 ms	3916 KB	Output is correct
12	Correct	18 ms	3532 KB	Output is correct
13	Correct	19 ms	3592 KB	Output is correct
14	Correct	19 ms	3600 KB	Output is correct
15	Correct	20 ms	3820 KB	Output is correct
16	Correct	20 ms	3880 KB	Output is correct
17	Correct	20 ms	3876 KB	Output is correct
18	Correct	20 ms	3872 KB	Output is correct
19	Correct	20 ms	3868 KB	Output is correct
20	Correct	17 ms	4768 KB	Output is correct
21	Correct	16 ms	4636 KB	Output is correct
22	Correct	22 ms	4484 KB	Output is correct
23	Correct	22 ms	4360 KB	Output is correct
24	Correct	25 ms	4360 KB	Output is correct
25	Correct	25 ms	4352 KB	Output is correct
26	Correct	20 ms	4312 KB	Output is correct
27	Correct	22 ms	4692 KB	Output is correct
28	Correct	22 ms	4568 KB	Output is correct
29	Correct	19 ms	4336 KB	Output is correct
30	Correct	19 ms	4544 KB	Output is correct
31	Correct	2 ms	620 KB	Output is correct
32	Correct	2 ms	628 KB	Output is correct
33	Correct	2 ms	752 KB	Output is correct
34	Incorrect	2 ms	620 KB	Wrong Answer [7]
35	Halted	0 ms	0 KB	-

답안 #394519

Compilation message

Subtask #1 0 / 8.0

Subtask #2 0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 53.0 / 55.0

Subtask #5 0 / 17.0

Subtask #1
0 / 8.0

Subtask #2
0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
53.0 / 55.0

Subtask #5
0 / 17.0