#include "Joi.h"
#include <vector>
const int BITS = 60;
void dfs(int v, int& t, int mp, std::vector<int>& tin, std::vector<int>& used, std::vector<int>& p, const std::vector<std::vector<int>>& g, std::vector<std::vector<int>>& childs, std::vector<int>& sz) {
tin[v] = t++;
p[v] = mp;
sz[v] = 1;
if (t >= BITS) {
t -= BITS;
}
used[v] = 1;
for (auto& u : g[v]) {
if (used[u] == 0) {
childs[v].push_back(u);
dfs(u, t, v, tin, used, p, g, childs, sz);
sz[v] += sz[u];
}
}
}
void Joi(int N, int M, int A[], int B[], long long x, int T) {
std::vector<std::vector<int>> g(N);
for (int i = 0; i < M; ++i) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
std::vector<int> tin(N), used(N), p(N), sz(N);
int t = 0;
std::vector<std::vector<int>> childs(N);
dfs(0, t, 0, tin, used, p, g, childs, sz);
for (int i = 0; i < N; ++i) {
MessageBoard(i, (x >> tin[i]) & 1);
}
return;
}
#include "Ioi.h"
#include <vector>
const int BITS = 60;
int Mov(int u) {
return Move(u);
}
void dfs(int v, int& t, int mp, std::vector<int>& tin, std::vector<int>& used, std::vector<int>& p, const std::vector<std::vector<int>>& g, std::vector<std::vector<int>>& childs, std::vector<int>& sz) {
tin[v] = t++;
p[v] = mp;
sz[v] = 1;
if (t >= BITS) {
t -= BITS;
}
used[v] = 1;
for (auto& u : g[v]) {
if (used[u] == 0) {
childs[v].push_back(u);
dfs(u, t, v, tin, used, p, g, childs, sz);
sz[v] += sz[u];
}
}
}
void dfs_down(int v, long long val, long long& ans, const std::vector<std::vector<int>>& childs, std::vector<int>& getted, const std::vector<int>& tin) {
getted[tin[v]] += 1;
getted[tin[v] + BITS] += 1;
ans += val << tin[v];
for (auto& u : childs[v]) {
if (getted[tin[u]] == 0) {
long long new_val = Mov(u);
dfs_down(u, new_val, ans, childs, getted, tin);
Mov(v);
}
}
}
void dfs2(int v, int& t, std::vector<int>& tin, std::vector<int>& tout, const std::vector<std::vector<int>>& childs) {
tin[v] = t++;
for (auto& u : childs[v]) {
dfs2(u, t, tin, tout, childs);
}
tout[v] = t - 1;
}
void dfs_twice(int v, long long val, long long& ans, int l, int r, int ql, int qr, const std::vector<std::vector<int>>& childs, const std::vector<int>& tin2, const std::vector<int>& tout2, const std::vector<int>& tin, std::vector<int>& getted) {
ans += val << tin[v];
getted[tin2[v]] += 1;
for (auto& u : childs[v]) {
int qql = tin2[u], qqr = std::min(tout2[u], qr);
if (qql > qr) {
break;
}
if ((l <= qql && qqr <= r) || (l <= qql + BITS && qqr + BITS <= r)) {
continue;
}
long long new_val = Mov(u);
dfs_twice(u, new_val, ans, l, r, qql, qqr, childs, tin2, tout2, tin, getted);
Mov(v);
}
}
void dfs_once(int v, long long val, long long& ans, int l, int r, int ql, int qr, const std::vector<std::vector<int>>& childs, const std::vector<int>& tin2, const std::vector<int>& tout2, const std::vector<int>& tin, std::vector<int>& getted) {
if (getted[tin2[v]] == 0) {
ans += val << tin[v];
getted[tin2[v]] += 1;
}
int last = -1;
for (auto& u : childs[v]) {
int qql = tin2[u], qqr = std::min(tout2[u], qr);
if (qql > qr) {
break;
}
if ((l <= qql && qqr <= r) || (l <= qql + BITS && qqr + BITS <= r)) {
continue;
}
if ((qql <= r && r < qqr) || (qql + BITS <= r && r < qqr + BITS)) {
last = u;
} else {
long long new_val = Mov(u);
dfs_twice(u, new_val, ans, l, r, ql, qr, childs, tin2, tout2, tin, getted);
Mov(v);
}
}
if (last != -1) {
int u = last;
long long new_val = Mov(u);
int qql = tin2[u], qqr = std::min(tout2[u], qr);
dfs_once(u, new_val, ans, l, r, qql, qqr, childs, tin2, tout2, tin, getted);
}
}
void get_h(int v, int qr, const std::vector<std::vector<int>>& childs, std::vector<int>& h, std::vector<int>& tin2) {
h[v] = 0;
for (auto& u : childs[v]) {
if (tin2[u] > qr) {
break;
}
get_h(u, qr, childs, h, tin2);
h[v] = std::max(h[v], h[u] + 1);
}
}
int get_str(int v, const std::vector<std::vector<int>>& childs, const std::vector<int>& sz, const std::vector<int>& p, std::vector<int>& h) {
int cur_p = -1, k = 0;
while (sz[v] < BITS) {
cur_p = v;
v = p[v];
k++;
}
if (cur_p == -1) {
return -1;
}
std::vector<int> tin2(h.size()), tout2(h.size());
int t = 0;
dfs2(v, t, tin2, tout2, childs);
get_h(v, tin2[v] + BITS - 1, childs, h, tin2);
if (h[v] < 10) {
return -1;
} else {
return 1;
}
}
void dfs_ans(int v, int qr, long long val, long long& ans, std::vector<int>& h, std::vector<int>& tin2, std::vector<int>& getted, const std::vector<std::vector<int>>& childs) {
ans += val << tin2[v] % BITS;
int last = -1;
for (auto& u : childs[v]) {
if (tin2[u] > qr) {
break;
}
if (h[u] == h[v] - 1 && last == -1) {
last = u;
} else {
long long new_val = Mov(u);
dfs_ans(u, qr, new_val, ans, h, tin2, getted, childs);
Mov(v);
}
}
if (last != -1) {
long long new_val = Mov(last);
dfs_ans(last, qr, new_val, ans, h, tin2, getted, childs);
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
std::vector<std::vector<int>> g(N);
for (int i = 0; i < M; ++i) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
std::vector<int> tin(N), used(N), p(N), sz(N), h(N);
int t = 0;
std::vector<std::vector<int>> childs(N);
dfs(0, t, 0, tin, used, p, g, childs, sz);
int str = get_str(P, childs, sz, p, h);
std::vector<int> getted(2 * BITS);
if (str != 0) {
int cur_v = P, cur_p = -1;
long long cur_val = V, ans = 0;
while (sz[cur_v] < BITS) {
dfs_down(cur_v, cur_val, ans, childs, getted, tin);
cur_p = cur_v;
cur_v = p[cur_v];
cur_val = Mov(cur_v);
}
CNT_ONCE = h[cur_v];
if (cur_p != -1) {
int k = tin[cur_v];
int l = tin[cur_p];
if (l < k) {
l += BITS;
}
std::vector<int> tin2(N), tout2(N);
t = k;
dfs2(cur_v, t, tin2, tout2, childs);
int r = l + tout2[cur_p] - tin2[cur_p];
dfs_once(cur_v, cur_val, ans, l, r, k, k + BITS - 1, childs, tin2, tout2, tin, getted);
} else {
int k = tin[cur_v];
int l = -1;
std::vector<int> tin2(N), tout2(N);
t = k;
dfs2(cur_v, t, tin2, tout2, childs);
int r = -1;
dfs_twice(cur_v, cur_val, ans, l, r, k, k + BITS - 1, childs, tin2, tout2, tin, getted);
}
return ans;
} else {
fl = true;
int cur_v = P;
long long cur_val = V, ans = 0;
while (sz[cur_v] < BITS) {
cur_v = p[cur_v];
cur_val = Mov(cur_v);
}
std::vector<int> tin2(N), tout2(N);
t = tin[cur_v];
dfs2(cur_v, t, tin2, tout2, childs);
dfs_ans(cur_v, tin[cur_v] + BITS - 1, cur_val, ans, h, tin2, getted, childs);
return ans;
}
}
Compilation message
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:169:9: error: 'CNT_ONCE' was not declared in this scope
169 | CNT_ONCE = h[cur_v];
| ^~~~~~~~
Ioi.cpp:192:9: error: 'fl' was not declared in this scope
192 | fl = true;
| ^~
