oj.uz

답안 #1021063

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1021063 2024-07-12T13:31:53 Z 0npata Amusement Park (JOI17_amusement_park) C++14
18 / 100
 20 ms 5668 KB 
#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); };

#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(cnt--) 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 1808 KB Output is correct
2 Correct 2 ms 1820 KB Output is correct
3 Correct 1 ms 1820 KB Output is correct
4 Correct 2 ms 1808 KB Output is correct
5 Correct 1 ms 1824 KB Output is correct
6 Correct 2 ms 1812 KB Output is correct
7 Correct 1 ms 1824 KB Output is correct
8 Correct 2 ms 1820 KB Output is correct
9 Correct 2 ms 1828 KB Output is correct
10 Correct 2 ms 1824 KB Output is correct
11 Correct 3 ms 2400 KB Output is correct
12 Correct 2 ms 1812 KB Output is correct
13 Correct 2 ms 1820 KB Output is correct
14 Correct 2 ms 1828 KB Output is correct
15 Correct 2 ms 1816 KB Output is correct
16 Correct 1 ms 1828 KB Output is correct
17 Correct 2 ms 1828 KB Output is correct
18 Correct 1 ms 1816 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 5664 KB Output is correct
2 Correct 18 ms 5668 KB Output is correct
3 Correct 19 ms 5640 KB Output is correct
4 Correct 10 ms 3908 KB Output is correct
5 Correct 11 ms 4672 KB Output is correct
6 Correct 11 ms 4296 KB Output is correct
7 Correct 12 ms 4412 KB Output is correct
8 Correct 11 ms 4676 KB Output is correct
9 Correct 11 ms 4676 KB Output is correct
10 Correct 9 ms 3900 KB Output is correct
11 Correct 10 ms 3904 KB Output is correct
12 Correct 10 ms 3880 KB Output is correct
13 Correct 10 ms 3616 KB Output is correct
14 Incorrect 10 ms 3896 KB Wrong Answer [7]
15 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1812 KB Output is correct
3 Correct 2 ms 1808 KB Output is correct
4 Correct 2 ms 2604 KB Output is correct
5 Correct 2 ms 2360 KB Output is correct
6 Correct 3 ms 2360 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 5332 KB Output is correct
10 Correct 8 ms 5336 KB Output is correct
11 Correct 9 ms 5456 KB Output is correct
12 Correct 0 ms 1820 KB Output is correct
13 Correct 1 ms 1804 KB Output is correct
14 Correct 1 ms 1800 KB Output is correct
15 Correct 2 ms 1848 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 5476 KB Output is correct
2 Correct 17 ms 5468 KB Output is correct
3 Correct 19 ms 5472 KB Output is correct
4 Correct 10 ms 3544 KB Output is correct
5 Correct 11 ms 5084 KB Output is correct
6 Correct 12 ms 4576 KB Output is correct
7 Correct 11 ms 4576 KB Output is correct
8 Correct 14 ms 4180 KB Output is correct
9 Correct 14 ms 4064 KB Output is correct
10 Correct 11 ms 3548 KB Output is correct
11 Correct 15 ms 3540 KB Output is correct
12 Correct 9 ms 3528 KB Output is correct
13 Correct 13 ms 3524 KB Output is correct
14 Incorrect 9 ms 3544 KB Wrong Answer [7]
15 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 5248 KB Output is correct
2 Correct 20 ms 5516 KB Output is correct
3 Correct 18 ms 5620 KB Output is correct
4 Correct 12 ms 3544 KB Output is correct
5 Correct 13 ms 5336 KB Output is correct
6 Correct 11 ms 4056 KB Output is correct
7 Correct 11 ms 4056 KB Output is correct
8 Correct 11 ms 4820 KB Output is correct
9 Correct 11 ms 4324 KB Output is correct
10 Correct 9 ms 3544 KB Output is correct
11 Correct 11 ms 3548 KB Output is correct
12 Correct 16 ms 3684 KB Output is correct
13 Correct 10 ms 3540 KB Output is correct
14 Incorrect 10 ms 3540 KB Wrong Answer [7]
15 Halted 0 ms 0 KB -