답안 #1021071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1021071	2024-07-12T13:38:54 Z	0npata	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	20 ms	6056 KB

Joi

#include "Joi.h"

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

#define vec vector

namespace joi {

const int MXN = 10'005;

int t = 0;

vec<int> tree[MXN];
int depth[MXN];
int ind[MXN];
vec<int> g[MXN];

void dfs1(int u, vec<bool>& vis) {
	vis[u] = true;
	for(int v : g[u]) {
		if(vis[v]) continue;
		dfs1(v, vis);
		depth[u] = max(depth[u], 1+depth[v]);
		tree[u].push_back(v);
	}
	sort(tree[u].begin(), tree[u].end(), [&](int x, int y) { return depth[x] == depth[y] ? x < y : depth[x] > depth[y]; });
}

void dfs2(int u) {
	ind[u] = t;
	t += 1;
	for(int v : tree[u]) {
		dfs2(v);
	}
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {

	vec<bool> vis(N);

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


	dfs1(0, vis);

	dfs2(0);


	for(int i = 0; i < N; i++){
		int bi = ind[i] % 60;

		int val = (X & ((long long)1<<bi)) != 0;
		MessageBoard(i, val);

	}
}

}


void Joi(int N, int M, int A[], int B[], long long X, int T) { joi::Joi(N, M, A, B, X, T); };

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>

using namespace std;

#define vec vector

namespace ioi {


	const int MXN = 10'005;

	vec<int> g[MXN];
	int par[MXN];
	int sz[MXN];

	vec<int> vals(MXN, -1);

	int t = 0;

	vec<int> tree[MXN];
	int depth[MXN];
	int ind[MXN];

	void dfs1(int u, vec<bool>& vis) {
		vis[u] = true;
		sz[u] = 1;
		for(int v : g[u]) {
			if(vis[v]) continue;
			par[v] = u;
			dfs1(v, vis);
			depth[u] = max(depth[u], 1+depth[v]);
			sz[u] += sz[v];
			tree[u].push_back(v);
		}
		sort(tree[u].begin(), tree[u].end(), [&](int x, int y) { return depth[x] == depth[y] ? x < y : depth[x] > depth[y]; });
	}

	void dfs2(int u) {
		ind[u] = t++;
		for(int v : tree[u]) {
			dfs2(v);
		}
	}

	void dfs3(int u, vec<int>& mvs, int rem) {
		rem -= 1;
		for(int v : tree[u]) {
			if(rem <= 0) {
				return;
			}
			mvs.push_back(v);
			dfs3(v, mvs, rem);
			rem -= sz[v];
			mvs.push_back(u);
		}
	}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	for(int i = 0; i<M; i++) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}

	vec<bool> vis(N);
	dfs1(0, vis);
	dfs2(0);

	long long x = 0;

	vals[P] = V;

	int cur = P;
	int cnt = 0;
	while(sz[cur] < 60) {
		cnt++;
		int cur_val = Move(par[cur]);

		cur = par[cur];

		vals[cur] = cur_val;
	}

	vec<int> mvs(0);

	dfs3(cur, mvs, 60);

	reverse(mvs.begin(), mvs.end());

	while(mvs.size() > 1 && depth[mvs.back()] > depth[mvs[mvs.size()-2]]) mvs.pop_back();

	for(int i = 1; i<mvs.size(); i++) {
		int nxt = mvs[i];
		vals[nxt] = Move(nxt);
	}

	for(int i = 0; i<N; i++) {
		if(vals[i] != -1) {
			int bi = ind[i]%60;
			x |= (((long long)vals[i]) << bi);
		}
	}
	return x;
}
}


long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) { return ioi::Ioi(N, M, A, B, P, V, T); }

Compilation message

Ioi.cpp: In function 'long long int ioi::Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i = 1; i<mvs.size(); i++) {
      |                 ~^~~~~~~~~~~

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1820 KB	Output is correct
2	Correct	2 ms	1816 KB	Output is correct
3	Correct	2 ms	1816 KB	Output is correct
4	Correct	1 ms	1808 KB	Output is correct
5	Correct	2 ms	1804 KB	Output is correct
6	Correct	1 ms	2060 KB	Output is correct
7	Correct	2 ms	1824 KB	Output is correct
8	Correct	1 ms	1816 KB	Output is correct
9	Correct	1 ms	1808 KB	Output is correct
10	Correct	2 ms	1820 KB	Output is correct
11	Correct	3 ms	2376 KB	Output is correct
12	Correct	1 ms	1820 KB	Output is correct
13	Correct	2 ms	1816 KB	Output is correct
14	Correct	2 ms	1840 KB	Output is correct
15	Correct	2 ms	1816 KB	Output is correct
16	Correct	2 ms	1812 KB	Output is correct
17	Correct	2 ms	1824 KB	Output is correct
18	Correct	1 ms	1824 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	5472 KB	Output is correct
2	Correct	16 ms	5484 KB	Output is correct
3	Correct	17 ms	5464 KB	Output is correct
4	Correct	11 ms	3552 KB	Output is correct
5	Correct	12 ms	4572 KB	Output is correct
6	Correct	11 ms	4056 KB	Output is correct
7	Correct	11 ms	4064 KB	Output is correct
8	Correct	10 ms	4580 KB	Output is correct
9	Correct	11 ms	4580 KB	Output is correct
10	Correct	10 ms	3548 KB	Output is correct
11	Correct	10 ms	3540 KB	Output is correct
12	Correct	9 ms	3524 KB	Output is correct
13	Correct	9 ms	3528 KB	Output is correct
14	Correct	11 ms	3536 KB	Output is correct
15	Correct	12 ms	4148 KB	Output is correct
16	Correct	12 ms	4416 KB	Output is correct
17	Correct	11 ms	3908 KB	Output is correct
18	Correct	11 ms	3904 KB	Output is correct
19	Correct	11 ms	3900 KB	Output is correct
20	Correct	8 ms	4668 KB	Output is correct
21	Correct	7 ms	4664 KB	Output is correct
22	Correct	14 ms	4160 KB	Output is correct
23	Correct	12 ms	4660 KB	Output is correct
24	Correct	10 ms	4160 KB	Output is correct
25	Correct	11 ms	4420 KB	Output is correct
26	Correct	11 ms	4668 KB	Output is correct
27	Correct	11 ms	4660 KB	Output is correct
28	Correct	11 ms	4668 KB	Output is correct
29	Correct	13 ms	4132 KB	Output is correct
30	Correct	13 ms	4152 KB	Output is correct
31	Correct	1 ms	1824 KB	Output is correct
32	Correct	1 ms	1824 KB	Output is correct
33	Correct	1 ms	1840 KB	Output is correct
34	Correct	2 ms	1820 KB	Output is correct
35	Correct	1 ms	1812 KB	Output is correct
36	Correct	1 ms	1808 KB	Output is correct
37	Correct	2 ms	1808 KB	Output is correct
38	Correct	1 ms	1824 KB	Output is correct
39	Correct	1 ms	1808 KB	Output is correct
40	Correct	2 ms	1812 KB	Output is correct
41	Correct	2 ms	1812 KB	Output is correct
42	Correct	2 ms	1812 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1808 KB	Output is correct
2	Correct	0 ms	1820 KB	Output is correct
3	Correct	2 ms	1800 KB	Output is correct
4	Correct	2 ms	2352 KB	Output is correct
5	Correct	3 ms	2348 KB	Output is correct
6	Correct	3 ms	2356 KB	Output is correct
7	Correct	3 ms	2360 KB	Output is correct
8	Correct	2 ms	2356 KB	Output is correct
9	Correct	8 ms	5344 KB	Output is correct
10	Correct	9 ms	5336 KB	Output is correct
11	Correct	11 ms	6056 KB	Output is correct
12	Correct	2 ms	1820 KB	Output is correct
13	Correct	2 ms	1808 KB	Output is correct
14	Correct	2 ms	1820 KB	Output is correct
15	Correct	1 ms	1808 KB	Output is correct

Subtask #4

55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	5216 KB	Output is correct
2	Correct	19 ms	5464 KB	Output is correct
3	Correct	18 ms	5476 KB	Output is correct
4	Correct	10 ms	3812 KB	Output is correct
5	Correct	11 ms	5088 KB	Output is correct
6	Correct	11 ms	4572 KB	Output is correct
7	Correct	11 ms	4568 KB	Output is correct
8	Correct	11 ms	4056 KB	Output is correct
9	Correct	12 ms	4076 KB	Output is correct
10	Correct	11 ms	3552 KB	Output is correct
11	Correct	10 ms	3544 KB	Output is correct
12	Correct	9 ms	3528 KB	Output is correct
13	Correct	10 ms	3528 KB	Output is correct
14	Correct	9 ms	3548 KB	Output is correct
15	Correct	11 ms	4356 KB	Output is correct
16	Correct	11 ms	4148 KB	Output is correct
17	Correct	11 ms	3896 KB	Output is correct
18	Correct	13 ms	3888 KB	Output is correct
19	Correct	11 ms	3900 KB	Output is correct
20	Correct	8 ms	4664 KB	Output is correct
21	Correct	9 ms	4744 KB	Output is correct
22	Correct	11 ms	4420 KB	Output is correct
23	Correct	12 ms	4412 KB	Output is correct
24	Correct	11 ms	4416 KB	Output is correct
25	Correct	11 ms	4668 KB	Output is correct
26	Correct	11 ms	4660 KB	Output is correct
27	Correct	11 ms	4664 KB	Output is correct
28	Correct	12 ms	4160 KB	Output is correct
29	Correct	11 ms	4152 KB	Output is correct
30	Correct	12 ms	4140 KB	Output is correct

Subtask #5

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	5264 KB	Output is correct
2	Correct	17 ms	5480 KB	Output is correct
3	Correct	18 ms	5472 KB	Output is correct
4	Correct	10 ms	3808 KB	Output is correct
5	Correct	11 ms	5396 KB	Output is correct
6	Correct	11 ms	4056 KB	Output is correct
7	Correct	12 ms	4068 KB	Output is correct
8	Correct	10 ms	4576 KB	Output is correct
9	Correct	11 ms	4312 KB	Output is correct
10	Correct	11 ms	3536 KB	Output is correct
11	Correct	9 ms	3552 KB	Output is correct
12	Correct	10 ms	3532 KB	Output is correct
13	Correct	9 ms	3528 KB	Output is correct
14	Correct	11 ms	3532 KB	Output is correct
15	Correct	10 ms	4156 KB	Output is correct
16	Correct	11 ms	4156 KB	Output is correct
17	Correct	13 ms	3892 KB	Output is correct
18	Correct	11 ms	3904 KB	Output is correct
19	Correct	15 ms	3812 KB	Output is correct
20	Correct	9 ms	4664 KB	Output is correct
21	Correct	9 ms	4664 KB	Output is correct
22	Correct	11 ms	4412 KB	Output is correct
23	Correct	11 ms	4408 KB	Output is correct
24	Correct	12 ms	4404 KB	Output is correct
25	Correct	11 ms	4408 KB	Output is correct
26	Correct	12 ms	4348 KB	Output is correct
27	Correct	11 ms	4664 KB	Output is correct
28	Correct	11 ms	4608 KB	Output is correct
29	Correct	12 ms	4384 KB	Output is correct
30	Correct	10 ms	4324 KB	Output is correct
31	Correct	1 ms	1804 KB	Output is correct
32	Correct	1 ms	1812 KB	Output is correct
33	Correct	3 ms	1820 KB	Output is correct
34	Correct	2 ms	1824 KB	Output is correct
35	Correct	2 ms	1808 KB	Output is correct
36	Correct	2 ms	1812 KB	Output is correct
37	Correct	1 ms	1812 KB	Output is correct
38	Correct	1 ms	1812 KB	Output is correct
39	Correct	1 ms	1824 KB	Output is correct
40	Correct	1 ms	1812 KB	Output is correct
41	Correct	1 ms	1820 KB	Output is correct
42	Correct	1 ms	1812 KB	Output is correct