oj.uz

답안 #203897

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203897 2020-02-22T23:46:52 Z staniewzki Amusement Park (JOI17_amusement_park) C++14
10 / 100
 65 ms 12532 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) {
	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]);
	}
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 860 KB Output is correct
2 Correct 10 ms 936 KB Output is correct
3 Correct 11 ms 1244 KB Output is correct
4 Incorrect 10 ms 968 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 11860 KB Output is correct
2 Correct 63 ms 12304 KB Output is correct
3 Correct 63 ms 12320 KB Output is correct
4 Incorrect 49 ms 9908 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 960 KB Output is correct
2 Correct 10 ms 800 KB Output is correct
3 Correct 10 ms 952 KB Output is correct
4 Correct 15 ms 2740 KB Output is correct
5 Correct 15 ms 2812 KB Output is correct
6 Correct 15 ms 2640 KB Output is correct
7 Correct 15 ms 2796 KB Output is correct
8 Correct 16 ms 2772 KB Output is correct
9 Correct 44 ms 12528 KB Output is correct
10 Correct 44 ms 12532 KB Output is correct
11 Correct 51 ms 12464 KB Output is correct
12 Correct 9 ms 980 KB Output is correct
13 Correct 10 ms 976 KB Output is correct
14 Correct 9 ms 980 KB Output is correct
15 Correct 10 ms 984 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 12052 KB Output is correct
2 Correct 65 ms 12476 KB Output is correct
3 Correct 62 ms 12324 KB Output is correct
4 Correct 49 ms 10132 KB Output is correct
5 Correct 50 ms 11824 KB Output is correct
6 Incorrect 51 ms 11148 KB Wrong Answer [7]
7 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 12064 KB Output is correct
2 Correct 62 ms 12328 KB Output is correct
3 Correct 62 ms 12328 KB Output is correct
4 Incorrect 49 ms 10004 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -