oj.uz

Submission #123022

# Submission time Handle Problem Language Result Execution time Memory
123022 2019-06-30T03:04:41 Z onjo0127 Amusement Park (JOI17_amusement_park) C++14
100 / 100
 332 ms 16832 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

struct TREE {
	vector<pii> edge;
	
	int getleaf(int x) {
		map<int, int> deg;
		for(auto& it: edge) {
			int x, y; tie(x, y) = it;
			++deg[x]; ++deg[y];
		}
		int ret = -1;
		for(auto& it: deg) if(it.second == 1 && it.first != x) ret = it.first;
		return ret;
	}
};

static TREE change(TREE T, int d, int a, int b) {
	TREE ret;
	for(auto& it: T.edge) if(it.first != d && it.second != d) ret.edge.push_back(it);
	ret.edge.push_back({a, b});
	return ret;
}

static TREE T[10009];
static int sid[10009], num[10009], c = 1;
static vector<int> adj[10009];
static bool vs[10009];

static int bit = 61;

static int d = 0;
static void dfs(int x) {
	num[x] = d++; sid[x] = 1; vs[x] = 1;
	for(auto& it: adj[x]) if(!vs[it] && d < bit) {
		T[1].edge.push_back({x, it});
		dfs(it);
	}
}

static void go(int x, int p) {
	vs[x] = 1;
	if(sid[x] == 0) {
		sid[x] = ++c;
		int del = T[sid[p]].getleaf(p);
		num[x] = num[del];
		T[c] = change(T[sid[p]], del, p, x);
	}
	for(auto& it: adj[x]) if(!vs[it]) go(it, x);
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	for(int i=0; i<M; i++) {
		int u = A[i], v = B[i];
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(0);
	memset(vs, 0, sizeof(vs));
	go(0, 0);
	for(int i=0; i<N; i++) {
		// printf("i: %d, sid: %d, num: %d\n", i, sid[i], num[i]);
		MessageBoard(i, (X >> num[i]) & 1);
	}
}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

struct TREE {
	vector<pii> edge;
	
	int getleaf(int x) {
		map<int, int> deg;
		for(auto& it: edge) {
			int x, y; tie(x, y) = it;
			++deg[x]; ++deg[y];
		}
		int ret = -1;
		for(auto& it: deg) if(it.second == 1 && it.first != x) ret = it.first;
		return ret;
	}
};

static TREE change(TREE T, int d, int a, int b) {
	TREE ret;
	for(auto& it: T.edge) if(it.first != d && it.second != d) ret.edge.push_back(it);
	ret.edge.push_back({a, b});
	return ret;
}

static TREE T[10009];
static int sid[10009], num[10009], c = 1;
static vector<int> adj[10009];
static bool vs[10009];

static int bit = 61;

static int d = 0;
static void dfs(int x) {
	num[x] = d++; sid[x] = 1; vs[x] = 1;
	for(auto& it: adj[x]) if(!vs[it] && d < bit) {
		T[1].edge.push_back({x, it});
		dfs(it);
	}
}

static void go(int x, int p) {
	vs[x] = 1;
	if(sid[x] == 0) {
		sid[x] = ++c;
		int del = T[sid[p]].getleaf(p);
		num[x] = num[del];
		T[c] = change(T[sid[p]], del, p, x);
	}
	for(auto& it: adj[x]) if(!vs[it]) go(it, x);
}

static long long ret;
static bool vis[10009];

static void getans(int tid, int now, int x, int par) {
	// printf("tid: %d, now: %d, x: %d, par: %d, num[now]: %d\n", tid, now, x, par, num[now]);
	vis[now] = 1;
	ret |= ((1LL*x) << (num[now]));
	for(auto& it: T[tid].edge) {
		int u, v; tie(u, v) = it;
		if(v == now) swap(u, v);
		if(u == now && !vis[v]) getans(tid, v, Move(v), now);
	}
	if(par != -1) Move(par);
}

int move(int x) {
	// printf("dest: %d\n", x);
	return Move(x);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	for(int i=0; i<M; i++) {
		int u = A[i], v = B[i];
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(0);
	memset(vs, 0, sizeof(vs));
	go(0, 0);
	getans(sid[P], P, V, -1);
	return ret;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1780 KB Output is correct
2 Correct 6 ms 1912 KB Output is correct
3 Correct 8 ms 2168 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 6 ms 1912 KB Output is correct
6 Correct 6 ms 1776 KB Output is correct
7 Correct 9 ms 2040 KB Output is correct
8 Correct 8 ms 2040 KB Output is correct
9 Correct 8 ms 2044 KB Output is correct
10 Correct 6 ms 1776 KB Output is correct
11 Correct 10 ms 2276 KB Output is correct
12 Correct 4 ms 1652 KB Output is correct
13 Correct 8 ms 2284 KB Output is correct
14 Correct 8 ms 2288 KB Output is correct
15 Correct 8 ms 2168 KB Output is correct
16 Correct 8 ms 2172 KB Output is correct
17 Correct 8 ms 2040 KB Output is correct
18 Correct 8 ms 2040 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 16516 KB Output is correct
2 Correct 241 ms 16448 KB Output is correct
3 Correct 234 ms 16348 KB Output is correct
4 Correct 142 ms 13808 KB Output is correct
5 Correct 332 ms 15168 KB Output is correct
6 Correct 206 ms 14664 KB Output is correct
7 Correct 205 ms 14600 KB Output is correct
8 Correct 203 ms 15096 KB Output is correct
9 Correct 201 ms 14988 KB Output is correct
10 Correct 131 ms 13808 KB Output is correct
11 Correct 136 ms 13684 KB Output is correct
12 Correct 133 ms 12484 KB Output is correct
13 Correct 133 ms 12456 KB Output is correct
14 Correct 139 ms 12980 KB Output is correct
15 Correct 155 ms 13496 KB Output is correct
16 Correct 154 ms 13628 KB Output is correct
17 Correct 151 ms 13676 KB Output is correct
18 Correct 145 ms 13644 KB Output is correct
19 Correct 150 ms 13768 KB Output is correct
20 Correct 146 ms 15164 KB Output is correct
21 Correct 142 ms 15160 KB Output is correct
22 Correct 240 ms 14584 KB Output is correct
23 Correct 219 ms 14908 KB Output is correct
24 Correct 219 ms 14392 KB Output is correct
25 Correct 219 ms 14652 KB Output is correct
26 Correct 219 ms 15024 KB Output is correct
27 Correct 220 ms 14912 KB Output is correct
28 Correct 222 ms 15116 KB Output is correct
29 Correct 199 ms 13608 KB Output is correct
30 Correct 207 ms 14128 KB Output is correct
31 Correct 6 ms 1776 KB Output is correct
32 Correct 6 ms 1904 KB Output is correct
33 Correct 8 ms 2176 KB Output is correct
34 Correct 6 ms 1904 KB Output is correct
35 Correct 5 ms 1776 KB Output is correct
36 Correct 4 ms 1784 KB Output is correct
37 Correct 4 ms 1968 KB Output is correct
38 Correct 4 ms 1776 KB Output is correct
39 Correct 4 ms 1648 KB Output is correct
40 Correct 6 ms 1988 KB Output is correct
41 Correct 6 ms 1992 KB Output is correct
42 Correct 4 ms 1648 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1864 KB Output is correct
2 Correct 5 ms 1776 KB Output is correct
3 Correct 5 ms 1912 KB Output is correct
4 Correct 28 ms 4112 KB Output is correct
5 Correct 28 ms 4080 KB Output is correct
6 Correct 28 ms 4248 KB Output is correct
7 Correct 26 ms 4112 KB Output is correct
8 Correct 26 ms 4248 KB Output is correct
9 Correct 147 ms 16796 KB Output is correct
10 Correct 143 ms 16816 KB Output is correct
11 Correct 144 ms 16832 KB Output is correct
12 Correct 6 ms 1648 KB Output is correct
13 Correct 6 ms 2032 KB Output is correct
14 Correct 5 ms 1776 KB Output is correct
15 Correct 5 ms 1804 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 16336 KB Output is correct
2 Correct 235 ms 16532 KB Output is correct
3 Correct 235 ms 16540 KB Output is correct
4 Correct 145 ms 13624 KB Output is correct
5 Correct 228 ms 16052 KB Output is correct
6 Correct 203 ms 14940 KB Output is correct
7 Correct 204 ms 14940 KB Output is correct
8 Correct 206 ms 14516 KB Output is correct
9 Correct 207 ms 14648 KB Output is correct
10 Correct 131 ms 13624 KB Output is correct
11 Correct 130 ms 13808 KB Output is correct
12 Correct 134 ms 12328 KB Output is correct
13 Correct 132 ms 12512 KB Output is correct
14 Correct 138 ms 12996 KB Output is correct
15 Correct 150 ms 13588 KB Output is correct
16 Correct 160 ms 13544 KB Output is correct
17 Correct 145 ms 13632 KB Output is correct
18 Correct 149 ms 13676 KB Output is correct
19 Correct 151 ms 13808 KB Output is correct
20 Correct 145 ms 15260 KB Output is correct
21 Correct 142 ms 15160 KB Output is correct
22 Correct 225 ms 15000 KB Output is correct
23 Correct 221 ms 14660 KB Output is correct
24 Correct 224 ms 14768 KB Output is correct
25 Correct 218 ms 15032 KB Output is correct
26 Correct 218 ms 15012 KB Output is correct
27 Correct 220 ms 15168 KB Output is correct
28 Correct 217 ms 14676 KB Output is correct
29 Correct 197 ms 13620 KB Output is correct
30 Correct 207 ms 14236 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 16420 KB Output is correct
2 Correct 232 ms 16460 KB Output is correct
3 Correct 232 ms 16456 KB Output is correct
4 Correct 154 ms 13732 KB Output is correct
5 Correct 229 ms 16532 KB Output is correct
6 Correct 213 ms 14476 KB Output is correct
7 Correct 220 ms 14412 KB Output is correct
8 Correct 209 ms 15204 KB Output is correct
9 Correct 206 ms 14784 KB Output is correct
10 Correct 130 ms 13628 KB Output is correct
11 Correct 131 ms 13796 KB Output is correct
12 Correct 133 ms 12560 KB Output is correct
13 Correct 132 ms 12688 KB Output is correct
14 Correct 139 ms 13080 KB Output is correct
15 Correct 160 ms 13760 KB Output is correct
16 Correct 153 ms 13408 KB Output is correct
17 Correct 149 ms 13724 KB Output is correct
18 Correct 149 ms 13564 KB Output is correct
19 Correct 156 ms 13732 KB Output is correct
20 Correct 143 ms 15280 KB Output is correct
21 Correct 142 ms 15124 KB Output is correct
22 Correct 219 ms 14820 KB Output is correct
23 Correct 221 ms 14648 KB Output is correct
24 Correct 224 ms 14776 KB Output is correct
25 Correct 218 ms 14748 KB Output is correct
26 Correct 221 ms 14648 KB Output is correct
27 Correct 219 ms 15132 KB Output is correct
28 Correct 218 ms 15384 KB Output is correct
29 Correct 200 ms 14100 KB Output is correct
30 Correct 208 ms 14476 KB Output is correct
31 Correct 6 ms 1904 KB Output is correct
32 Correct 6 ms 1984 KB Output is correct
33 Correct 7 ms 2040 KB Output is correct
34 Correct 6 ms 1992 KB Output is correct
35 Correct 6 ms 1912 KB Output is correct
36 Correct 5 ms 1776 KB Output is correct
37 Correct 4 ms 1904 KB Output is correct
38 Correct 6 ms 1884 KB Output is correct
39 Correct 5 ms 1788 KB Output is correct
40 Correct 6 ms 1788 KB Output is correct
41 Correct 6 ms 1776 KB Output is correct
42 Correct 5 ms 1648 KB Output is correct