#include "Joi.h"
/*
Wei Wai Wei Wai
Zumigat nan damu dimi kwayt rayt
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
ull b, m;
FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
ull reduce(ull a) {
ull q = (ull)((L(m) * a) >> 64);
ull r = a - q * b; // can be proven that 0 <= r < 2*b
return r >= b ? r - b : r;
}
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
static void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
static void debug_out(Head H, Tail... T) {
cerr << " " << H;
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e4 + 10;
static int n, m, dsu[maxn], a[maxn], b[maxn], h[maxn], sz[maxn], mxh[maxn], val[maxn], par[maxn], root;
static vector<int> g[maxn], going;
static bool flg = false;
static int getdsu(int v){
return (dsu[v] == -1? v: dsu[v] = getdsu(dsu[v]));
}
static void merge(int u, int v){
int x = getdsu(u), y = getdsu(v);
if (x == y) return;
g[u].push_back(v);
g[v].push_back(u);
dsu[v] = u;
}
static void dfs(int v, int p = -1){
sz[v] = 1;
mxh[v] = h[v];
par[v] = p;
for (auto u: g[v]){
if (u != p){
h[u] = h[v] + 1;
dfs(u, v);
sz[v] += sz[u];
mxh[v] = max(mxh[v], mxh[u]);
}
}
}
static void dfs(int v, int x, bool b, int p = -1){
val[v] = x - 1;
going.push_back(v);
if (x == 1) return;
x--;
int bc = -1;
for (auto u: g[v]){
if (u != p && (bc == -1 || mxh[u] > mxh[bc])) bc = u;
}
int tmp = min(x, sz[bc]);
x -= tmp;
for (auto u: g[v]){
if (u != p && u != bc && x != 0){
dfs(u, min(x, sz[u]), false, v);
going.push_back(v);
x -= min(x, sz[u]);
}
}
dfs(bc, tmp, b, v);
if (!b) going.push_back(v);
}
static void solve(){
memset(dsu, -1, sizeof dsu);
for (int i = 0; i < m; i++) merge(a[i], b[i]);
dfs(0);
int root = max_element(h, h+n) - h;
h[root] = 0;
dfs(root);
int mx = max_element(h, h+n) - h;
if (h[mx] >= 59){
flg = true;
return;
}
dfs(root, 60, true);
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
n = N;
m = M;
for (int i = 0; i < m; i++){
a[i] = A[i];
b[i] = B[i];
}
solve();
for (int i = 0; i < n; i++){
if (flg) MessageBoard(i, (X >> (h[i]%60)) & 1);
else MessageBoard(i, (X >> val[i]) & 1);
}
}
#include "Ioi.h"
/*
Wei Wai Wei Wai
Zumigat nan damu dimi kwayt rayt
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
ull b, m;
FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
ull reduce(ull a) {
ull q = (ull)((L(m) * a) >> 64);
ull r = a - q * b; // can be proven that 0 <= r < 2*b
return r >= b ? r - b : r;
}
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
static void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
static void debug_out(Head H, Tail... T) {
cerr << " " << H;
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e4 + 10;
static int n, m, dsu[maxn], a[maxn], b[maxn], h[maxn], sz[maxn], mxh[maxn], val[maxn], par[maxn], root;
static vector<int> g[maxn], going;
static bool flg = false;
static int getdsu(int v){
return (dsu[v] == -1? v: dsu[v] = getdsu(dsu[v]));
}
static void merge(int u, int v){
int x = getdsu(u), y = getdsu(v);
if (x == y) return;
g[u].push_back(v);
g[v].push_back(u);
dsu[v] = u;
}
static void dfs(int v, int p = -1){
sz[v] = 1;
mxh[v] = h[v];
par[v] = p;
for (auto u: g[v]){
if (u != p){
h[u] = h[v] + 1;
dfs(u, v);
sz[v] += sz[u];
mxh[v] = max(mxh[v], mxh[u]);
}
}
}
static void dfs(int v, int x, bool b, int p = -1){
val[v] = x - 1;
going.push_back(v);
if (x == 1) return;
x--;
int bc = -1;
for (auto u: g[v]){
if (u != p && (bc == -1 || mxh[u] > mxh[bc])) bc = u;
}
int tmp = min(x, sz[bc]);
x -= tmp;
for (auto u: g[v]){
if (u != p && u != bc && x != 0){
dfs(u, min(x, sz[u]), false, v);
going.push_back(v);
x -= min(x, sz[u]);
}
}
dfs(bc, tmp, b, v);
if (!b) going.push_back(v);
}
static void solve(){
memset(dsu, -1, sizeof dsu);
for (int i = 0; i < m; i++) merge(a[i], b[i]);
dfs(0);
int root = max_element(h, h+n) - h;
h[root] = 0;
dfs(root);
int mx = max_element(h, h+n) - h;
if (h[mx] >= 59){
flg = true;
return;
}
dfs(root, 60, true);
}
static ll Calc(int v, ll x, int k = 0, int p = -1){
ll res = (x << k);
if (k == 59) return res;
int bc = -1;
for (auto u: g[v]){
if (u != p && (bc == -1 || mxh[bc] < mxh[u])) bc = u;
}
return res + Calc(bc, Move(bc), k+1, v);
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
n = N;
m = M;
for (int i = 0; i < m; i++){
a[i] = A[i];
b[i] = B[i];
}
solve();
ll ans = 0;
if (flg){
if (h[P] >= 59){
int v = P;
int x = V;
do{
ans += (x << (h[v] % 60));
x = Move(par[v]);
v = par[v];
} while(h[v] % 60 != h[P]%60);
return ans;
}
int v = P;
int x = V;
while(par[v] != -1){
x = Move(par[v]);
v = par[v];
}
return Calc(v, x);
}
int v = P;
ll x = V;
while(par[v] != -1){
x = Move(par[v]);
v = par[v];
}
for (int i = 0; i < going.size(); i++){
ans |= (x << val[v]);
if (i + 1 != going.size()){
x = Move(going[i+1]);
v = going[i+1];
}
}
return ans;
}
Compilation message
Joi.cpp:48:99: warning: 'root' defined but not used [-Wunused-variable]
48 | static int n, m, dsu[maxn], a[maxn], b[maxn], h[maxn], sz[maxn], mxh[maxn], val[maxn], par[maxn], root;
| ^~~~
Joi.cpp:30:13: warning: 'void debug_out()' defined but not used [-Wunused-function]
30 | static void debug_out() { cerr << endl; }
| ^~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:158:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for (int i = 0; i < going.size(); i++){
| ~~^~~~~~~~~~~~~~
Ioi.cpp:160:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | if (i + 1 != going.size()){
| ~~~~~~^~~~~~~~~~~~~~~
Ioi.cpp: At global scope:
Ioi.cpp:48:99: warning: 'root' defined but not used [-Wunused-variable]
48 | static int n, m, dsu[maxn], a[maxn], b[maxn], h[maxn], sz[maxn], mxh[maxn], val[maxn], par[maxn], root;
| ^~~~
Ioi.cpp:30:13: warning: 'void debug_out()' defined but not used [-Wunused-function]
30 | static void debug_out() { cerr << endl; }
| ^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1284 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
165 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1288 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
153 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
156 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
