| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 249612 | staniewzki | Amusement Park (JOI17_amusement_park) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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])));
}
#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;
}