oj.uz

Submission #203896

# Submission time Handle Problem Language Result Execution time Memory
203896 2020-02-22T23:30:36 Z staniewzki Amusement Park (JOI17_amusement_park) C++14
0 / 100
 67 ms 12340 KB 
#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;
vector<int> dep, 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);
		}
	}
}

vector<vector<int>> subtree;
vector<int> val;

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];
		PII min_dep = {1e9, -1}, max_dep = {-1, -1};
		for(int u : subtree[p]) {
			min_dep = min(min_dep, {dep[u], u});
			max_dep = max(max_dep, {dep[u], u});
		}
		int leaf = (min_dep.ND == p ? max_dep.ND : 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();
}

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])));
}

#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;
vector<int> dep, 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);
		}
	}
}

vector<vector<int>> subtree;
vector<int> val;

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];
		PII min_dep = {1e9, -1}, max_dep = {-1, -1};
		for(int u : subtree[p]) {
			min_dep = min(min_dep, {dep[u], u});
			max_dep = max(max_dep, {dep[u], u});
		}
		int leaf = (min_dep.ND == p ? max_dep.ND : 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) {
	x += (1LL << val[v]) * q[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]);
	}
	preprocess(n);
	in = q = vector<int>(n);
	q[p] = v;
	for(int u : subtree[p])
		in[u] = true;
	dfs(p);
	return x;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 896 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 12340 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 936 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 12336 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 12324 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -