| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 112838 | MAMBA | 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>
#include "Joi.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back
constexpr int N = 1e4 + 10;
void Joi(int n, int m, int a[] , int b[], ll x , int t) {
init(n , m , a , b);
if (len >= 60) {
rep(i , 0 , n)
MessageBoard(i , (x >> (lvl[i] % 60)) & 1);
}
else {
int root2 = max_element(lvl , lvl + n) - lvl;
m1.reset();
dfs2(root , root2);
dfs3(root);
rep(i , 0 , n)
MessageBoard(i , (x >> (val[i] - 1)) & 1);
}
return;
}
#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back
constexpr int N = 1e4 + 10;
ll res , cnt;
int root = -1, len = -1;
int lvl[N], val[N];
vi adj[N];
bitset<N << 1> m1, m2;
void dfs0(int v, int a[], int b[]) {
m1[v] = true;
for (auto e : adj[v]) {
int u = v ^ a[e] ^ b[e];
if (!m1[u]) {
m2[e] = true;
dfs0(u, a, b);
}
}
}
void dfs1(int v, int par = -1) {
for (auto e : adj[v])
if (par ^ e) {
lvl[e] = lvl[v] + 1;
dfs1(e , v);
}
}
bool dfs2(int v , int dst , int par = -1) {
for (auto e :adj[v])
if (e ^ par && dfs2(e , dst , v)) {
m1[v] = true;
val[v] = ++cnt;
return true;
}
}
void dfs3(int v, int par = -1) {
if (!m1[v]) val[v] = ++cnt;
for (auto e :adj[v])
if (e ^ par)
dfs3(e , v);
}
inline void init(int n , int m , int a[], int b[]) {
res = 0;
cnt = 0;
m1.reset();
m2.reset();
rep(i , 0 , n) adj[i].clear();
rep(i , 0 , m)
{ adj[a[i]].pb(i);
adj[b[i]].pb(i);
}
dfs0(0, a, b);
rep(i , 0 , n) adj[i].clear();
rep(i , 0 , m) if(m2[i]) {
adj[a[i]].pb(b[i]);
adj[b[i]].pb(a[i]);
}
lvl[0] = 1;
dfs1(0);
root = max_element(lvl , lvl + n) - lvl;
lvl[root] = 1;
dfs1(root);
len = *max_element(lvl , lvl + n);
return;
}
void dfs4(int v, int &p , int &me, int par = -1) {
res |= (1ll * me) << (val[v] - 1);
for (auto e : adj[v])
if (e ^ par && !m1[e] && val[e] <= 60) {
me = Move(e);
p = e;
dfs4(e , p , me , v);
}
for (auto e :adj[v])
if (e ^ par && m1[e] && val[e] <= 60) {
me = Move(e);
p = e;
dfs4(e , p , me , v);
}
if (!m1[v]) {
me = Move(par);
p = par;
}
}
ll Ioi(int n, int m, int a[], int b[], int p ,int me, int t) {
init(n , m , a , b);
if (len >= 60) {
m1.reset();
dfs2(p , root);
if (lvl[p] >= 60) {
rep(i , 0 , 60) {
res |= (1ll * me) << (lvl[p] % 60);
for (auto e : adj[p])
if (m1[e]) {
me = Move(e);
m1[p] = false;
p = e;
break;
}
}
}
else {
while(true) {
bool flag = false;
for (auto e : adj[p])
if (m1[e]) {
me = Move(e);
m1[p] = false;
flag = true;
p = e;
break;
}
if (!flag) break;
}
int root2 = max_element(lvl , lvl + n) - lvl;
dfs2(p , root2);
rep(i , 0 , 60) {
res |= (1ll * me) << (lvl[p] % 60);
for (auto e : adj[p])
if (m1[e]) {
me = Move(e);
m1[p] = false;
p = e;
break;
}
}
}
return res;
}
////////////////////////////////////////
int root2 = max_element(lvl , lvl + n) - lvl;
m1.reset();
dfs2(p ,root);
while(true) {
bool flag = false;
for (auto e : adj[p])
if (m1[e]) {
me = Move(e);
m1[p] = false;
flag = true;
p = e;
break;
}
if (!flag) break;
}
cnt = 0;
m1.reset();
dfs2(root , root2);
dfs3(root);
m1.reset();
dfs4(root, p , me);
return res;
}