Submission #249613

#	Time	Username	Problem	Language	Result	Execution time	Memory
249613		staniewzki	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	68 ms	12772 KiB

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 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17