#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);
}
}
struct Tree {
map<int, set<int>> edges;
void dfs(int v, vector<int> &path, int f = -1) {
path.pb(v);
for (int u : g[v]) {
if (u == f) {
continue;
}
dfs(u, path, v);
path.pb(v);
}
}
int find_leaf() {
for (auto &it : edges) {
if (sz(it.second) == 1) {
return it.first;
}
}
assert(0);
return -1;
}
int extract_leaf() {
int v = find_leaf();
int u = *edges[v].begin();
edges[u].erase(v);
edges.erase(v);
return v;
}
void add_edge(int u, int v) {
edges[u].insert(v);
edges[v].insert(u);
}
};
static Tree wtf[N];
static void easy_find(int v) {
if (sz(wtf[center].edges) == K) {
return;
}
for (int u : g[v]) {
wtf[center].add_edge(v, u);
easy_find(u);
if (sz(wtf[center].edges) == K) {
return;
}
}
}
static void meow(int v) {
if (wtf[v].edges.empty()) {
wtf[v] = wtf[p[v]];
int col = what[wtf[v].extract_leaf()];
what[v] = col;
wtf[v].add_edge(v, p[v]);
}
for (int u : g[v]) {
meow(u);
}
}
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 {
easy_find(center);
int ptr = 0;
for (auto &it : wtf[center].edges) {
int u = it.first;
what[u] = ptr++;
if (u != center) wtf[u] = wtf[center];
}
meow(center);
rep(i, 0, n) {
assert(sz(wtf[i].edges) == K);
vector<bool> col(K);
for (auto &it : wtf[i].edges) {
int u = it.first;
col[what[u]] = 1;
}
rep(i, 0, K) assert(col[i]);
}
}
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);
}
}
struct Tree {
map<int, set<int>> edges;
void dfs(int v, vector<int> &path, int f = -1) {
path.pb(v);
for (int u : g[v]) {
if (u == f) {
continue;
}
dfs(u, path, v);
path.pb(v);
}
}
int find_leaf() {
for (auto &it : edges) {
if (sz(it.second) == 1) {
return it.first;
}
}
assert(0);
return -1;
}
int extract_leaf() {
int v = find_leaf();
int u = *edges[v].begin();
edges[u].erase(v);
edges.erase(v);
return v;
}
void add_edge(int u, int v) {
edges[u].insert(v);
edges[v].insert(u);
}
vector<int> get_path(int start) {
vector<int> res;
dfs(start, res);
return res;
}
};
static Tree wtf[N];
static void easy_find(int v) {
if (sz(wtf[center].edges) == K) {
return;
}
for (int u : g[v]) {
wtf[center].add_edge(v, u);
easy_find(u);
if (sz(wtf[center].edges) == K) {
return;
}
}
}
static void meow(int v) {
if (wtf[v].edges.empty()) {
wtf[v] = wtf[p[v]];
int col = what[wtf[v].extract_leaf()];
what[v] = col;
wtf[v].add_edge(v, p[v]);
}
for (int u : g[v]) {
meow(u);
}
}
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;
}
int v;
void go(int to) {
static int steps = 0;
steps++;
assert(steps <= 500);
assert(0 <= to && to <= n - 1);
int x = Move(to);
v = to;
know[what[v]] = x;
}
long long Ioi(int nn, int mm, int A[], int B[], int vv, int num, int T) {
rep(i, 0, K) know[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);
v = vv;
if (dist[center] >= K - 1) {
periodic_color(center, 0, +1);
know[what[v]] = num;
while (p[v] != -1) {
go(p[v]);
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];
});
go(u);
}
} else {
easy_find(center);
int ptr = 0;
for (auto &it : wtf[center].edges) {
int u = it.first;
what[u] = ptr++;
if (u != center) wtf[u] = wtf[center];
}
meow(center);
rep(i, 0, n) {
vector<bool> col(K);
for (auto &it : wtf[i].edges) {
int u = it.first;
col[what[u]] = 1;
}
}
vector<int> path = wtf[v].get_path(v);
for (int u : path) {
go(u);
}
}
return answer();
}
Compilation message
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) {
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
5280 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
6080 KB |
Output is correct |
| 2 |
Correct |
38 ms |
6104 KB |
Output is correct |
| 3 |
Correct |
37 ms |
6180 KB |
Output is correct |
| 4 |
Runtime error |
325 ms |
230692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
461384 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
461384 KB |
Output is correct |
| 2 |
Correct |
41 ms |
461384 KB |
Output is correct |
| 3 |
Correct |
38 ms |
461384 KB |
Output is correct |
| 4 |
Runtime error |
287 ms |
230692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
461384 KB |
Output is correct |
| 2 |
Correct |
41 ms |
461384 KB |
Output is correct |
| 3 |
Correct |
46 ms |
461384 KB |
Output is correct |
| 4 |
Runtime error |
286 ms |
230692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
