oj.uz

Submission #123021

# Submission time Handle Problem Language Result Execution time Memory
123021 2019-06-30T03:03:47 Z onjo0127 Amusement Park (JOI17_amusement_park) C++14
100 / 100
 236 ms 17264 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) << (1LL*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 1876 KB Output is correct
2 Correct 6 ms 1960 KB Output is correct
3 Correct 8 ms 2260 KB Output is correct
4 Correct 6 ms 1916 KB Output is correct
5 Correct 6 ms 1976 KB Output is correct
6 Correct 6 ms 1916 KB Output is correct
7 Correct 8 ms 2024 KB Output is correct
8 Correct 8 ms 2172 KB Output is correct
9 Correct 8 ms 2052 KB Output is correct
10 Correct 6 ms 1780 KB Output is correct
11 Correct 9 ms 2288 KB Output is correct
12 Correct 4 ms 2016 KB Output is correct
13 Correct 8 ms 2052 KB Output is correct
14 Correct 8 ms 2296 KB Output is correct
15 Correct 8 ms 2044 KB Output is correct
16 Correct 8 ms 2276 KB Output is correct
17 Correct 8 ms 2184 KB Output is correct
18 Correct 8 ms 2172 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 16192 KB Output is correct
2 Correct 232 ms 16904 KB Output is correct
3 Correct 232 ms 16944 KB Output is correct
4 Correct 141 ms 13860 KB Output is correct
5 Correct 227 ms 15568 KB Output is correct
6 Correct 209 ms 14848 KB Output is correct
7 Correct 209 ms 15080 KB Output is correct
8 Correct 205 ms 15368 KB Output is correct
9 Correct 203 ms 15196 KB Output is correct
10 Correct 130 ms 13772 KB Output is correct
11 Correct 131 ms 13940 KB Output is correct
12 Correct 131 ms 12688 KB Output is correct
13 Correct 131 ms 12728 KB Output is correct
14 Correct 140 ms 13464 KB Output is correct
15 Correct 155 ms 13856 KB Output is correct
16 Correct 156 ms 13732 KB Output is correct
17 Correct 150 ms 13964 KB Output is correct
18 Correct 146 ms 13968 KB Output is correct
19 Correct 147 ms 13836 KB Output is correct
20 Correct 147 ms 15456 KB Output is correct
21 Correct 141 ms 15516 KB Output is correct
22 Correct 218 ms 14760 KB Output is correct
23 Correct 221 ms 15188 KB Output is correct
24 Correct 219 ms 14616 KB Output is correct
25 Correct 219 ms 15044 KB Output is correct
26 Correct 221 ms 15224 KB Output is correct
27 Correct 218 ms 15128 KB Output is correct
28 Correct 219 ms 15264 KB Output is correct
29 Correct 207 ms 14064 KB Output is correct
30 Correct 213 ms 14440 KB Output is correct
31 Correct 6 ms 1916 KB Output is correct
32 Correct 6 ms 1976 KB Output is correct
33 Correct 8 ms 2180 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 1916 KB Output is correct
37 Correct 4 ms 1908 KB Output is correct
38 Correct 4 ms 1788 KB Output is correct
39 Correct 4 ms 1896 KB Output is correct
40 Correct 5 ms 1820 KB Output is correct
41 Correct 6 ms 1780 KB Output is correct
42 Correct 4 ms 1780 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1912 KB Output is correct
2 Correct 5 ms 1916 KB Output is correct
3 Correct 4 ms 1904 KB Output is correct
4 Correct 26 ms 4336 KB Output is correct
5 Correct 27 ms 4180 KB Output is correct
6 Correct 26 ms 4248 KB Output is correct
7 Correct 26 ms 4344 KB Output is correct
8 Correct 26 ms 4248 KB Output is correct
9 Correct 143 ms 17204 KB Output is correct
10 Correct 143 ms 16676 KB Output is correct
11 Correct 143 ms 16932 KB Output is correct
12 Correct 4 ms 1784 KB Output is correct
13 Correct 4 ms 1904 KB Output is correct
14 Correct 4 ms 1776 KB Output is correct
15 Correct 4 ms 1916 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 16196 KB Output is correct
2 Correct 232 ms 17016 KB Output is correct
3 Correct 235 ms 17264 KB Output is correct
4 Correct 152 ms 13720 KB Output is correct
5 Correct 236 ms 16244 KB Output is correct
6 Correct 208 ms 15196 KB Output is correct
7 Correct 206 ms 15236 KB Output is correct
8 Correct 206 ms 14468 KB Output is correct
9 Correct 207 ms 14752 KB Output is correct
10 Correct 132 ms 14064 KB Output is correct
11 Correct 131 ms 13812 KB Output is correct
12 Correct 135 ms 12772 KB Output is correct
13 Correct 132 ms 12768 KB Output is correct
14 Correct 137 ms 13368 KB Output is correct
15 Correct 150 ms 13720 KB Output is correct
16 Correct 169 ms 13848 KB Output is correct
17 Correct 146 ms 13868 KB Output is correct
18 Correct 158 ms 13968 KB Output is correct
19 Correct 152 ms 13828 KB Output is correct
20 Correct 145 ms 15608 KB Output is correct
21 Correct 146 ms 15252 KB Output is correct
22 Correct 227 ms 15104 KB Output is correct
23 Correct 234 ms 14988 KB Output is correct
24 Correct 226 ms 14848 KB Output is correct
25 Correct 228 ms 15200 KB Output is correct
26 Correct 234 ms 15140 KB Output is correct
27 Correct 226 ms 15484 KB Output is correct
28 Correct 220 ms 14736 KB Output is correct
29 Correct 197 ms 13816 KB Output is correct
30 Correct 208 ms 14568 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 16560 KB Output is correct
2 Correct 235 ms 16736 KB Output is correct
3 Correct 232 ms 16908 KB Output is correct
4 Correct 150 ms 13888 KB Output is correct
5 Correct 228 ms 16816 KB Output is correct
6 Correct 218 ms 14844 KB Output is correct
7 Correct 205 ms 14812 KB Output is correct
8 Correct 203 ms 15208 KB Output is correct
9 Correct 205 ms 15008 KB Output is correct
10 Correct 130 ms 13864 KB Output is correct
11 Correct 131 ms 13860 KB Output is correct
12 Correct 132 ms 12696 KB Output is correct
13 Correct 138 ms 12812 KB Output is correct
14 Correct 140 ms 13292 KB Output is correct
15 Correct 166 ms 13864 KB Output is correct
16 Correct 152 ms 13828 KB Output is correct
17 Correct 146 ms 13964 KB Output is correct
18 Correct 148 ms 13856 KB Output is correct
19 Correct 159 ms 13880 KB Output is correct
20 Correct 144 ms 15640 KB Output is correct
21 Correct 142 ms 15384 KB Output is correct
22 Correct 225 ms 15136 KB Output is correct
23 Correct 222 ms 14752 KB Output is correct
24 Correct 219 ms 14800 KB Output is correct
25 Correct 218 ms 14876 KB Output is correct
26 Correct 218 ms 14616 KB Output is correct
27 Correct 220 ms 15384 KB Output is correct
28 Correct 219 ms 15384 KB Output is correct
29 Correct 205 ms 14172 KB Output is correct
30 Correct 209 ms 14484 KB Output is correct
31 Correct 6 ms 1780 KB Output is correct
32 Correct 6 ms 1920 KB Output is correct
33 Correct 8 ms 2292 KB Output is correct
34 Correct 6 ms 1788 KB Output is correct
35 Correct 6 ms 2000 KB Output is correct
36 Correct 5 ms 1788 KB Output is correct
37 Correct 4 ms 1780 KB Output is correct
38 Correct 5 ms 1884 KB Output is correct
39 Correct 4 ms 1916 KB Output is correct
40 Correct 6 ms 1920 KB Output is correct
41 Correct 6 ms 1916 KB Output is correct
42 Correct 5 ms 1916 KB Output is correct