# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1261628 | badge881 | Amusement Park (JOI17_amusement_park) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define MAXN 10007
using namespace std;
#include "Joi.h"
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
int n, m;
vector<int> v[MAXN];
const int bits = 60;
int bit[MAXN];
bool vis[MAXN], trav[MAXN];
vector<int> tree[MAXN], special;
int topsort[MAXN], sz;
int num;
function<void(int, int)> dfs = [&](int x, int p)
{
trav[x] = true;
if (num == bits)
return;
num++;
vis[x] = true;
special.push_back(x);
bit[x] = num - 1;
if (p != 0)
{
tree[p].push_back(x);
tree[x].push_back(p);
}
for (int i : v[x])
{
if (trav[i])
continue;
dfs(i, x);
}
}
function<void(int, int, int)>
dfs2 = [&](int x, int p, int root)
{
for (int i : tree[x])
{
if (i == p)
continue;
dfs2(i, x, root);
}
topsort[sz] = bit[x];
sz++;
}
function<void(int, int, int, int)>
dfs3 = [&](int x, int p, int pos, int id)
{
trav[x] = true;
if (!vis[x])
bit[x] = topsort[pos % bits];
for (int i : v[x])
{
if (trav[i] or vis[i])
continue;
dfs3(i, x, pos + 1, id);
}
}
n = N;
m = M;
for (int i = 0; i < m; i++)
{
A[i]++;
B[i]++;
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
A[i]--;
B[i]--;
}
for (int i = 1; i <= n; i++)
sort(v[i].begin(), v[i].end());
dfs(1, 0);
for (int i : special)
{
for (int f = 1; f <= n; f++)
trav[f] = false;
sz = 0;
dfs2(i, 0, i);
dfs3(i, 0, -1, i);
}
for (int i = 0; i < n; i++)
MessageBoard(i, ((1LL << bit[i + 1]) & X) > 0);
return;
}
#include <bits/stdc++.h>
#define MAXN 10007
using namespace std;
#include "Ioi.h"
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
int n, m, parent[MAXN];
vector<int> v[MAXN];
const int bits = 60;
int bit[MAXN];
bool vis[MAXN], trav[MAXN];
vector<int> tree[MAXN], special;
int topsort[MAXN], sz;
int num;
int sol[70];
bool used[70];
long long ans;
function<void(int, int)> dfs = [&](int x, int p) -> void
{
parent[x] = p;
trav[x] = true;
if (num < bits)
{
num++;
vis[x] = true;
special.push_back(x);
bit[x] = num - 1;
if (p != 0)
{
tree[p].push_back(x);
tree[x].push_back(p);
}
}
for (int i : v[x])
{
if (trav[i])
continue;
dfs(i, x);
}
}
function<void(int, int, int)> dfs2 = [&](int x, int p, int root) -> void
{
for (int i : tree[x])
{
if (i == p)
continue;
dfs2(i, x, root);
}
topsort[sz] = bit[x];
sz++;
}
function<void(int, int, int)> dfs3 = [&](int x, int p, int pos, int id) -> void
{
trav[x] = true;
if (!vis[x])
{
bit[x] = topsort[pos % bits];
}
for (int i : v[x])
{
if (trav[i] or vis[i])
continue;
dfs3(i, x, pos + 1, id);
}
}
function<void(int, int)> dfs4 = [&](int x, int curr) -> void
{
used[bit[x]] = true;
sol[bit[x]] = curr;
for (int i : tree[x])
{
if (!used[bit[i]])
{
dfs4(i, Move(i - 1));
Move(x - 1);
}
}
}
n = N;
m = M;
for (int i = 0; i < m; i++)
{
A[i]++;
B[i]++;
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
A[i]--;
B[i]--;
}
for (int i = 1; i <= n; i++)
sort(v[i].begin(), v[i].end());
dfs(1, 0);
for (int i : special)
{
for (int f = 1; f <= n; f++)
trav[f] = false;
sz = 0;
dfs2(i, 0, i);
dfs3(i, 0, -1, i);
}
P++;
used[bit[P]] = true;
sol[bit[P]] = V;
for (int i = 1; i <= bits - 1 and !vis[P]; i++)
{
P = parent[P];
V = Move(P - 1);
if (vis[P])
break;
used[bit[P]] = true;
sol[bit[P]] = V;
}
if (vis[P])
dfs4(P, V);
for (int i = 0; i < bits; i++)
ans += (long long)(1LL << i) * sol[i];
return ans;
}