#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int INF = (int) 1e9 + 1e6 + 123;
static const ll LINF = (ll) 1e18 + 1e9 + 123;
#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) (x).size())
#define mp make_pair
#define pb push_back
static bool mini(auto &x, const auto &y) {
if (y < x) {
x = y;
return 1;
}
return 0;
}
static bool maxi(auto &x, const auto &y) {
if (y > x) {
x = y;
return 1;
}
return 0;
}
static const int N = 20005;
static const int K = 60;
static int n;
static int p[N];
static vector<int> g[N];
static int get(int v) {
return (p[v] == v ? v : (p[v] = get(p[v])));
}
static bool unite(int u, int v) {
u = get(u), v = get(v);
if (u == v) {
return 0;
}
p[u] = v;
return 1;
}
static bool test(long long mask, int bit) {
return mask & (1LL << bit);
}
static void add_edge(int u, int v) {
g[u].pb(v);
g[v].pb(u);
}
static int center;
static int center_dist = INF;
static int dist[N];
static void calc_dist(int v, int f = -1) {
dist[v] = 0;
for (int u : g[v]) {
if (u == f) {
continue;
}
calc_dist(u, v);
maxi(dist[v], dist[u] + 1);
}
}
static void find_center(int v, int f = -1, int up = 0) {
int max_dist = max(up, dist[v]);
if (mini(center_dist, max_dist)) {
center = v;
}
multiset<int> q;
for (int u : g[v]) {
if (u == f) {
continue;
}
q.insert(dist[u] + 2);
}
for (int u : g[v]) {
if (u == f) {
continue;
}
q.erase(q.find(dist[u] + 2));
int nup = up + 1;
if (sz(q)) {
maxi(nup, *q.rbegin());
}
find_center(u, v, nup);
q.insert(dist[u] + 2);
}
}
static void make_root(int v, int f = -1) {
p[v] = f;
int ptr = 0;
int pos = -1;
for (int u : g[v]) {
if (u == f) {
pos = ptr;
ptr++;
continue;
}
make_root(u, v);
ptr++;
}
if (pos != -1) {
g[v].erase(g[v].begin() + pos);
}
}
static int what[N];
static void periodic_color(int v, int c, int dir) {
what[v] = c;
for (int u : g[v]) {
periodic_color(u, (c + dir + K) % K, dir);
}
}
void Joi(int nn, int mm, int A[], int B[], long long x, int T) {
n = nn;
rep(i, 0, n) p[i] = i;
rep(i, 0, mm) {
if (unite(A[i], B[i])) {
add_edge(A[i], B[i]);
}
}
calc_dist(0);
find_center(0);
make_root(center);
calc_dist(center);
if (dist[center] >= K - 1) {
periodic_color(center, 0, +1);
} else {
what[center] = 0;
vector<pair<int, int>> q;
for (int u : g[center]) {
q.pb({dist[u], u});
}
sort(all(q));
reverse(all(q));
int ptr = K - 1;
for (auto &it : q) {
int u = it.second;
periodic_color(u, ptr, -1);
ptr -= dist[u] + 1;
if (ptr <= 0) {
break;
}
}
}
rep(i, 0, n) {
MessageBoard(i, test(x, what[i]));
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int INF = (int) 1e9 + 1e6 + 123;
static const ll LINF = (ll) 1e18 + 1e9 + 123;
#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) (x).size())
#define mp make_pair
#define pb push_back
static bool mini(auto &x, const auto &y) {
if (y < x) {
x = y;
return 1;
}
return 0;
}
static bool maxi(auto &x, const auto &y) {
if (y > x) {
x = y;
return 1;
}
return 0;
}
static const int N = 20005;
static const int K = 60;
static int n;
static int p[N];
static vector<int> g[N];
static int get(int v) {
return (p[v] == v ? v : (p[v] = get(p[v])));
}
static bool unite(int u, int v) {
u = get(u), v = get(v);
if (u == v) {
return 0;
}
p[u] = v;
return 1;
}
static bool test(long long mask, int bit) {
return mask & (1LL << bit);
}
static void add_edge(int u, int v) {
g[u].pb(v);
g[v].pb(u);
}
static int center;
static int center_dist = INF;
static int dist[N];
static void calc_dist(int v, int f = -1) {
dist[v] = 0;
for (int u : g[v]) {
if (u == f) {
continue;
}
calc_dist(u, v);
maxi(dist[v], dist[u] + 1);
}
}
static void find_center(int v, int f = -1, int up = 0) {
int max_dist = max(up, dist[v]);
if (mini(center_dist, max_dist)) {
center = v;
}
multiset<int> q;
for (int u : g[v]) {
if (u == f) {
continue;
}
q.insert(dist[u] + 2);
}
for (int u : g[v]) {
if (u == f) {
continue;
}
q.erase(q.find(dist[u] + 2));
int nup = up + 1;
if (sz(q)) {
maxi(nup, *q.rbegin());
}
find_center(u, v, nup);
q.insert(dist[u] + 2);
}
}
static void make_root(int v, int f = -1) {
p[v] = f;
int ptr = 0;
int pos = -1;
for (int u : g[v]) {
if (u == f) {
pos = ptr;
ptr++;
continue;
}
make_root(u, v);
ptr++;
}
if (pos != -1) {
g[v].erase(g[v].begin() + pos);
}
}
static int what[N];
static void periodic_color(int v, int c, int dir) {
what[v] = c;
for (int u : g[v]) {
periodic_color(u, (c + dir + K) % K, dir);
}
}
ll know[K];
bool known() {
rep(i, 0, K) {
if (know[i] == -1) {
return 0;
}
}
return 1;
}
ll answer() {
ll ans = 0;
rep(i, 0, K) {
ans += (know[i] << i);
}
return ans;
}
long long Ioi(int nn, int mm, int A[], int B[], int v, int num, int T) {
rep(i, 0, K) know[i] = -1;
set<pair<int, int>> wtf;
rep(i, 0, mm) {
wtf[{A[i], B[i]}] = 1;
wtf[{B[i], A[i]}] = 1;
}
n = nn;
rep(i, 0, n) p[i] = i;
rep(i, 0, mm) {
if (unite(A[i], B[i])) {
add_edge(A[i], B[i]);
}
}
calc_dist(0);
find_center(0);
make_root(center);
calc_dist(center);
if (dist[center] >= K - 1) {
periodic_color(center, 0, +1);
know[what[v]] = num;
while (p[v] != -1) {
assert(wtf.count({v, p[v]}));
num = Move(p[v]);
v = p[v];
know[what[v]] = num;
if (known()) {
break;
}
}
while (!known()) {
assert(sz(g[v]));
int u = *max_element(all(g[v]), [&] (int x, int y) {
return dist[x] < dist[y];
});
assert(wtf.count({v, u}));
num = Move(u);
v = u;
know[what[v]] = num;
}
} else {
what[center] = 0;
vector<pair<int, int>> q;
for (int u : g[center]) {
q.pb({dist[u], u});
}
sort(all(q));
reverse(all(q));
int ptr = K - 1;
for (auto &it : q) {
int u = it.second;
periodic_color(u, ptr, -1);
ptr -= dist[u] + 1;
if (ptr <= 0) {
break;
}
}
know[what[v]] = num;
while (p[v] != -1) {
num = Move(p[v]);
v = p[v];
know[what[v]] = num;
if (known()) {
break;
}
}
for (auto &it : q) {
if (known()) {
break;
}
assert(v == center);
int to = it.second;
num = Move(to);
v = to;
know[what[v]] = num;
while (sz(g[v]) && !known()) {
int u = *max_element(all(g[v]), [&] (int x, int y) {
return dist[x] < dist[y];
});
num = Move(u);
v = u;
know[what[v]] = num;
}
if (known()) {
break;
}
while (p[v] != -1) {
num = Move(p[v]);
v = p[v];
know[what[v]] = num;
if (known()) {
break;
}
}
}
}
return answer();
}
Compilation message
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:155:6: error: no match for 'operator[]' (operand types are 'std::set<std::pair<int, int> >' and '<brace-enclosed initializer list>')
wtf[{A[i], B[i]}] = 1;
^
Ioi.cpp:156:6: error: no match for 'operator[]' (operand types are 'std::set<std::pair<int, int> >' and '<brace-enclosed initializer list>')
wtf[{B[i], A[i]}] = 1;
^
Ioi.cpp: At global scope:
Ioi.cpp:54:13: warning: 'bool test(long long int, int)' defined but not used [-Wunused-function]
static bool test(long long mask, int bit) {
^~~~
