oj.uz

Submission #123023

# Submission time Handle Problem Language Result Execution time Memory
123023 2019-06-30T03:05:27 Z onjo0127 Amusement Park (JOI17_amusement_park) C++14
100 / 100
 237 ms 16996 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 = 60;

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 = 60;

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 4 ms 1776 KB Output is correct
2 Correct 6 ms 1904 KB Output is correct
3 Correct 8 ms 2124 KB Output is correct
4 Correct 6 ms 1916 KB Output is correct
5 Correct 6 ms 1904 KB Output is correct
6 Correct 8 ms 1944 KB Output is correct
7 Correct 10 ms 2176 KB Output is correct
8 Correct 8 ms 2048 KB Output is correct
9 Correct 8 ms 2176 KB Output is correct
10 Correct 6 ms 1912 KB Output is correct
11 Correct 10 ms 2264 KB Output is correct
12 Correct 5 ms 1816 KB Output is correct
13 Correct 8 ms 2168 KB Output is correct
14 Correct 8 ms 2204 KB Output is correct
15 Correct 9 ms 2040 KB Output is correct
16 Correct 8 ms 2132 KB Output is correct
17 Correct 9 ms 2168 KB Output is correct
18 Correct 8 ms 2128 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 16368 KB Output is correct
2 Correct 231 ms 16516 KB Output is correct
3 Correct 231 ms 16564 KB Output is correct
4 Correct 140 ms 13732 KB Output is correct
5 Correct 223 ms 15260 KB Output is correct
6 Correct 201 ms 14684 KB Output is correct
7 Correct 204 ms 14800 KB Output is correct
8 Correct 201 ms 15140 KB Output is correct
9 Correct 205 ms 14912 KB Output is correct
10 Correct 130 ms 13748 KB Output is correct
11 Correct 130 ms 13612 KB Output is correct
12 Correct 131 ms 12552 KB Output is correct
13 Correct 132 ms 12468 KB Output is correct
14 Correct 137 ms 13084 KB Output is correct
15 Correct 153 ms 13552 KB Output is correct
16 Correct 154 ms 13568 KB Output is correct
17 Correct 147 ms 13732 KB Output is correct
18 Correct 143 ms 13632 KB Output is correct
19 Correct 147 ms 13468 KB Output is correct
20 Correct 146 ms 15384 KB Output is correct
21 Correct 141 ms 15288 KB Output is correct
22 Correct 214 ms 14640 KB Output is correct
23 Correct 215 ms 14952 KB Output is correct
24 Correct 216 ms 14476 KB Output is correct
25 Correct 219 ms 14904 KB Output is correct
26 Correct 219 ms 15092 KB Output is correct
27 Correct 216 ms 15032 KB Output is correct
28 Correct 216 ms 15060 KB Output is correct
29 Correct 197 ms 13700 KB Output is correct
30 Correct 205 ms 14224 KB Output is correct
31 Correct 6 ms 1904 KB Output is correct
32 Correct 6 ms 1904 KB Output is correct
33 Correct 8 ms 2168 KB Output is correct
34 Correct 6 ms 1916 KB Output is correct
35 Correct 6 ms 1916 KB Output is correct
36 Correct 5 ms 1780 KB Output is correct
37 Correct 4 ms 1784 KB Output is correct
38 Correct 4 ms 1888 KB Output is correct
39 Correct 4 ms 1784 KB Output is correct
40 Correct 5 ms 1912 KB Output is correct
41 Correct 6 ms 1912 KB Output is correct
42 Correct 6 ms 1880 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1952 KB Output is correct
2 Correct 5 ms 1984 KB Output is correct
3 Correct 4 ms 1776 KB Output is correct
4 Correct 26 ms 4120 KB Output is correct
5 Correct 27 ms 4172 KB Output is correct
6 Correct 26 ms 4120 KB Output is correct
7 Correct 27 ms 4248 KB Output is correct
8 Correct 26 ms 4244 KB Output is correct
9 Correct 145 ms 16880 KB Output is correct
10 Correct 143 ms 16996 KB Output is correct
11 Correct 145 ms 16896 KB Output is correct
12 Correct 4 ms 1872 KB Output is correct
13 Correct 4 ms 1868 KB Output is correct
14 Correct 5 ms 1912 KB Output is correct
15 Correct 5 ms 1892 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 16312 KB Output is correct
2 Correct 237 ms 16604 KB Output is correct
3 Correct 232 ms 16536 KB Output is correct
4 Correct 143 ms 13644 KB Output is correct
5 Correct 223 ms 16104 KB Output is correct
6 Correct 201 ms 15032 KB Output is correct
7 Correct 205 ms 15052 KB Output is correct
8 Correct 203 ms 14284 KB Output is correct
9 Correct 202 ms 14520 KB Output is correct
10 Correct 133 ms 13700 KB Output is correct
11 Correct 134 ms 13760 KB Output is correct
12 Correct 136 ms 12664 KB Output is correct
13 Correct 130 ms 12544 KB Output is correct
14 Correct 133 ms 12848 KB Output is correct
15 Correct 148 ms 13552 KB Output is correct
16 Correct 160 ms 13660 KB Output is correct
17 Correct 146 ms 13636 KB Output is correct
18 Correct 148 ms 13708 KB Output is correct
19 Correct 146 ms 13636 KB Output is correct
20 Correct 143 ms 15320 KB Output is correct
21 Correct 147 ms 15064 KB Output is correct
22 Correct 219 ms 14872 KB Output is correct
23 Correct 216 ms 14852 KB Output is correct
24 Correct 215 ms 14668 KB Output is correct
25 Correct 216 ms 15104 KB Output is correct
26 Correct 215 ms 14908 KB Output is correct
27 Correct 216 ms 15344 KB Output is correct
28 Correct 216 ms 14520 KB Output is correct
29 Correct 196 ms 13688 KB Output is correct
30 Correct 205 ms 14264 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 16564 KB Output is correct
2 Correct 237 ms 16452 KB Output is correct
3 Correct 231 ms 16584 KB Output is correct
4 Correct 149 ms 13632 KB Output is correct
5 Correct 223 ms 16448 KB Output is correct
6 Correct 203 ms 14528 KB Output is correct
7 Correct 203 ms 14520 KB Output is correct
8 Correct 199 ms 14912 KB Output is correct
9 Correct 202 ms 14728 KB Output is correct
10 Correct 129 ms 13668 KB Output is correct
11 Correct 129 ms 13808 KB Output is correct
12 Correct 131 ms 12540 KB Output is correct
13 Correct 135 ms 12592 KB Output is correct
14 Correct 139 ms 13108 KB Output is correct
15 Correct 168 ms 13688 KB Output is correct
16 Correct 150 ms 13716 KB Output is correct
17 Correct 143 ms 13736 KB Output is correct
18 Correct 146 ms 13604 KB Output is correct
19 Correct 153 ms 13604 KB Output is correct
20 Correct 143 ms 15424 KB Output is correct
21 Correct 141 ms 15208 KB Output is correct
22 Correct 215 ms 14900 KB Output is correct
23 Correct 218 ms 14824 KB Output is correct
24 Correct 218 ms 14620 KB Output is correct
25 Correct 226 ms 15024 KB Output is correct
26 Correct 216 ms 14584 KB Output is correct
27 Correct 222 ms 15168 KB Output is correct
28 Correct 219 ms 15168 KB Output is correct
29 Correct 197 ms 14160 KB Output is correct
30 Correct 204 ms 14420 KB Output is correct
31 Correct 6 ms 1904 KB Output is correct
32 Correct 6 ms 1948 KB Output is correct
33 Correct 7 ms 2040 KB Output is correct
34 Correct 6 ms 1988 KB Output is correct
35 Correct 6 ms 1912 KB Output is correct
36 Correct 4 ms 1864 KB Output is correct
37 Correct 4 ms 1912 KB Output is correct
38 Correct 4 ms 1784 KB Output is correct
39 Correct 4 ms 1776 KB Output is correct
40 Correct 5 ms 1776 KB Output is correct
41 Correct 6 ms 1904 KB Output is correct
42 Correct 4 ms 2020 KB Output is correct