Submission #249613

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
249613	2020-07-15T11:13:15 Z	staniewzki	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	68 ms	12772 KB

Joi

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.ST << ", " << p.ND << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
template<class T> int size(T && a) { return a.size(); }
 
using LL = long long;
using PII = pair<int, int>;
 
#include "Joi.h"
 
vector<vector<int>> adj, tree, subtree;
vector<int> dep, par, val, is_par;
 
void gen_tree(int v = 0, int d = 0) {
	dep[v] = d;
	for(int u : adj[v]) {
		if(dep[u] == -1) {
			par[u] = v;
			tree[v].emplace_back(u);
			gen_tree(u, d + 1);
		}
	}
}
 
void init_subtree(int v = 0) {
	if(size(subtree[0]) == 60) return;
	val[v] = size(subtree[0]);
	subtree[0].emplace_back(v);
	for(int u : tree[v])
		init_subtree(u);
}
 
void cal_subtree(int v = 0) {
	if(size(subtree[v]) == 0) {
		int p = par[v], leaf = -1;
		for(int u : subtree[p])
			if(par[u] != -1)
				is_par[par[u]] = true;
		for(int u : subtree[p])
			if(u != p && !is_par[u])
				leaf = u;
		for(int u : subtree[p])
			if(par[u] != -1)
				is_par[par[u]] = false;
		if(leaf == -1) {
			PII min_dep = {1e9, -1};
			for(int u : subtree[p])
				min_dep = min(min_dep, {dep[u], u});
			leaf = min_dep.ND;
		}
		val[v] = val[leaf];
		subtree[v] = {v};
		for(int u : subtree[p]) if(u != leaf)
			subtree[v].emplace_back(u);
	}
 
	for(int u : tree[v])
		cal_subtree(u);
}
 
void preprocess(int n) {
	tree.resize(n);
	val = dep = par = vector<int>(n, -1);
	is_par.resize(n);
	subtree.resize(n);
	gen_tree();
	init_subtree();
	for(int v : subtree[0]) {
		if(v) subtree[v] = subtree[0];
	}
	cal_subtree();
}
 
void Joi(int n, int m, int a[], int b[], LL x, int t) {
	adj.resize(n);
	REP(i, m) {
		adj[a[i]].emplace_back(b[i]);
		adj[b[i]].emplace_back(a[i]);
	}
	preprocess(n);
	REP(i, n) MessageBoard(i, bool(x & (1LL << val[i])));
}

Ioi

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.ST << ", " << p.ND << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
template<class T> int size(T && a) { return a.size(); }
 
using LL = long long;
using PII = pair<int, int>;
 
#include "Ioi.h"
 
vector<vector<int>> adj, tree, subtree;
vector<int> dep, par, val, is_par;
 
void gen_tree(int v = 0, int d = 0) {
	dep[v] = d;
	for(int u : adj[v]) {
		if(dep[u] == -1) {
			par[u] = v;
			tree[v].emplace_back(u);
			gen_tree(u, d + 1);
		}
	}
}
 
void init_subtree(int v = 0) {
	if(size(subtree[0]) == 60) return;
	val[v] = size(subtree[0]);
	subtree[0].emplace_back(v);
	for(int u : tree[v])
		init_subtree(u);
}
 
void cal_subtree(int v = 0) {
	if(size(subtree[v]) == 0) {
		int p = par[v], leaf = -1;
		for(int u : subtree[p])
			if(par[u] != -1)
				is_par[par[u]] = true;
		for(int u : subtree[p])
			if(u != p && !is_par[u])
				leaf = u;
		for(int u : subtree[p])
			if(par[u] != -1)
				is_par[par[u]] = false;
		if(leaf == -1) {
			PII min_dep = {1e9, -1};
			for(int u : subtree[p])
				min_dep = min(min_dep, {dep[u], u});
			leaf = min_dep.ND;
		}
		val[v] = val[leaf];
		subtree[v] = {v};
		for(int u : subtree[p]) if(u != leaf)
			subtree[v].emplace_back(u);
	}
 
	for(int u : tree[v])
		cal_subtree(u);
}
 
void preprocess(int n) {
	tree.resize(n);
	val = dep = par = vector<int>(n, -1);
	subtree.resize(n);
	gen_tree();
	init_subtree();
	for(int v : subtree[0]) {
		if(v) subtree[v] = subtree[0];
	}
	cal_subtree();
}
 
LL x;
vector<int> in, q;
 
void dfs(int v) {
	in[v] = false;
	x += (1LL << val[v]) * q[v];
	tree[v].emplace_back(par[v]);
	for(int u : tree[v]) {
		if(in[u]) {
			q[u] = Move(u);
			dfs(u);
			Move(v);
		}
	}
}
 
LL Ioi(int n, int m, int a[], int b[], int p, int v, int t) {
	adj.resize(n);
	REP(i, m) {
		adj[a[i]].emplace_back(b[i]);
		adj[b[i]].emplace_back(a[i]);
	}
	in = q = is_par = vector<int>(n);
	preprocess(n);
	q[p] = v;
	for(int u : subtree[p])
		in[u] = true;
	dfs(p);
	return x;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	992 KB	Output is correct
2	Correct	2 ms	904 KB	Output is correct
3	Correct	2 ms	1140 KB	Output is correct
4	Correct	1 ms	776 KB	Output is correct
5	Correct	1 ms	968 KB	Output is correct
6	Correct	2 ms	776 KB	Output is correct
7	Correct	2 ms	1132 KB	Output is correct
8	Correct	2 ms	1276 KB	Output is correct
9	Correct	2 ms	1024 KB	Output is correct
10	Correct	1 ms	956 KB	Output is correct
11	Correct	5 ms	1280 KB	Output is correct
12	Correct	1 ms	988 KB	Output is correct
13	Correct	2 ms	1168 KB	Output is correct
14	Correct	2 ms	1040 KB	Output is correct
15	Correct	2 ms	1040 KB	Output is correct
16	Correct	2 ms	1168 KB	Output is correct
17	Correct	2 ms	1272 KB	Output is correct
18	Correct	2 ms	1040 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	12184 KB	Output is correct
2	Correct	67 ms	12476 KB	Output is correct
3	Correct	67 ms	12408 KB	Output is correct
4	Correct	50 ms	9972 KB	Output is correct
5	Correct	54 ms	11188 KB	Output is correct
6	Correct	59 ms	10844 KB	Output is correct
7	Correct	55 ms	10824 KB	Output is correct
8	Correct	54 ms	11092 KB	Output is correct
9	Correct	53 ms	11000 KB	Output is correct
10	Correct	51 ms	9656 KB	Output is correct
11	Correct	48 ms	9908 KB	Output is correct
12	Correct	46 ms	9176 KB	Output is correct
13	Correct	47 ms	9232 KB	Output is correct
14	Correct	48 ms	9392 KB	Output is correct
15	Correct	52 ms	10044 KB	Output is correct
16	Correct	50 ms	10036 KB	Output is correct
17	Correct	50 ms	9952 KB	Output is correct
18	Correct	52 ms	9952 KB	Output is correct
19	Correct	57 ms	9908 KB	Output is correct
20	Correct	49 ms	11192 KB	Output is correct
21	Correct	48 ms	10964 KB	Output is correct
22	Correct	54 ms	10588 KB	Output is correct
23	Correct	54 ms	11040 KB	Output is correct
24	Correct	53 ms	10776 KB	Output is correct
25	Correct	53 ms	10808 KB	Output is correct
26	Correct	53 ms	10796 KB	Output is correct
27	Correct	54 ms	10924 KB	Output is correct
28	Correct	53 ms	11004 KB	Output is correct
29	Correct	48 ms	9944 KB	Output is correct
30	Correct	50 ms	10292 KB	Output is correct
31	Correct	2 ms	964 KB	Output is correct
32	Correct	2 ms	904 KB	Output is correct
33	Correct	2 ms	1292 KB	Output is correct
34	Correct	2 ms	964 KB	Output is correct
35	Correct	1 ms	776 KB	Output is correct
36	Correct	2 ms	992 KB	Output is correct
37	Correct	1 ms	1012 KB	Output is correct
38	Correct	0 ms	776 KB	Output is correct
39	Correct	1 ms	1000 KB	Output is correct
40	Correct	1 ms	904 KB	Output is correct
41	Correct	2 ms	1032 KB	Output is correct
42	Correct	1 ms	1000 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	980 KB	Output is correct
2	Correct	0 ms	904 KB	Output is correct
3	Correct	1 ms	904 KB	Output is correct
4	Correct	8 ms	2756 KB	Output is correct
5	Correct	8 ms	2812 KB	Output is correct
6	Correct	8 ms	2628 KB	Output is correct
7	Correct	10 ms	2812 KB	Output is correct
8	Correct	8 ms	2812 KB	Output is correct
9	Correct	48 ms	12468 KB	Output is correct
10	Correct	48 ms	12772 KB	Output is correct
11	Correct	48 ms	12636 KB	Output is correct
12	Correct	0 ms	988 KB	Output is correct
13	Correct	0 ms	984 KB	Output is correct
14	Correct	1 ms	1120 KB	Output is correct
15	Correct	1 ms	1000 KB	Output is correct

Subtask #4

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	12440 KB	Output is correct
2	Correct	66 ms	12556 KB	Output is correct
3	Correct	67 ms	12308 KB	Output is correct
4	Correct	51 ms	9936 KB	Output is correct
5	Correct	59 ms	11924 KB	Output is correct
6	Correct	52 ms	10940 KB	Output is correct
7	Correct	55 ms	11016 KB	Output is correct
8	Correct	54 ms	10724 KB	Output is correct
9	Correct	54 ms	10764 KB	Output is correct
10	Correct	48 ms	9784 KB	Output is correct
11	Correct	48 ms	9788 KB	Output is correct
12	Correct	47 ms	9212 KB	Output is correct
13	Correct	47 ms	8996 KB	Output is correct
14	Correct	50 ms	9556 KB	Output is correct
15	Correct	53 ms	10268 KB	Output is correct
16	Correct	51 ms	10260 KB	Output is correct
17	Correct	52 ms	10200 KB	Output is correct
18	Correct	52 ms	9964 KB	Output is correct
19	Correct	52 ms	9948 KB	Output is correct
20	Correct	50 ms	11300 KB	Output is correct
21	Correct	48 ms	10932 KB	Output is correct
22	Correct	53 ms	11060 KB	Output is correct
23	Correct	53 ms	10728 KB	Output is correct
24	Correct	53 ms	10748 KB	Output is correct
25	Correct	53 ms	10940 KB	Output is correct
26	Correct	55 ms	10804 KB	Output is correct
27	Correct	53 ms	11080 KB	Output is correct
28	Correct	53 ms	10792 KB	Output is correct
29	Correct	49 ms	9884 KB	Output is correct
30	Correct	53 ms	10532 KB	Output is correct

Subtask #5

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	12316 KB	Output is correct
2	Correct	66 ms	12316 KB	Output is correct
3	Correct	67 ms	12548 KB	Output is correct
4	Correct	55 ms	10172 KB	Output is correct
5	Correct	54 ms	12280 KB	Output is correct
6	Correct	54 ms	10736 KB	Output is correct
7	Correct	53 ms	10764 KB	Output is correct
8	Correct	53 ms	11072 KB	Output is correct
9	Correct	53 ms	11044 KB	Output is correct
10	Correct	48 ms	9784 KB	Output is correct
11	Correct	50 ms	10028 KB	Output is correct
12	Correct	61 ms	9336 KB	Output is correct
13	Correct	53 ms	9208 KB	Output is correct
14	Correct	50 ms	9496 KB	Output is correct
15	Correct	57 ms	10148 KB	Output is correct
16	Correct	59 ms	10264 KB	Output is correct
17	Correct	52 ms	9948 KB	Output is correct
18	Correct	52 ms	9956 KB	Output is correct
19	Correct	51 ms	9956 KB	Output is correct
20	Correct	48 ms	11060 KB	Output is correct
21	Correct	52 ms	10984 KB	Output is correct
22	Correct	60 ms	10828 KB	Output is correct
23	Correct	54 ms	10548 KB	Output is correct
24	Correct	57 ms	10752 KB	Output is correct
25	Correct	54 ms	10728 KB	Output is correct
26	Correct	54 ms	10576 KB	Output is correct
27	Correct	54 ms	11068 KB	Output is correct
28	Correct	55 ms	11188 KB	Output is correct
29	Correct	48 ms	10148 KB	Output is correct
30	Correct	50 ms	10408 KB	Output is correct
31	Correct	2 ms	952 KB	Output is correct
32	Correct	2 ms	904 KB	Output is correct
33	Correct	2 ms	1168 KB	Output is correct
34	Correct	2 ms	952 KB	Output is correct
35	Correct	1 ms	980 KB	Output is correct
36	Correct	1 ms	776 KB	Output is correct
37	Correct	0 ms	904 KB	Output is correct
38	Correct	1 ms	1120 KB	Output is correct
39	Correct	1 ms	776 KB	Output is correct
40	Correct	1 ms	904 KB	Output is correct
41	Correct	0 ms	904 KB	Output is correct
42	Correct	1 ms	996 KB	Output is correct