#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back
constexpr int N = 1e4 + 10;
int root = -1, len = -1;
int lvl[N], val[N];
vi adj[N];
bitset<N << 1> m1, m2;
void dfs0(int v, int a[], int b[]) {
m1[v] = true;
for (auto e : adj[v]) {
int u = v ^ a[e] ^ b[e];
if (!m1[u]) {
m2[e] = true;
dfs0(u, a, b);
}
}
}
void dfs1(int v, int par = -1) {
for (auto e : adj[v])
if (par ^ e) {
lvl[e] = lvl[v] + 1;
dfs1(e , v);
}
}
int cnt;
bool dfs2(int v , int dst , int par = -1) {
if (v == dst) {
m1[v] =true;
val[v] = ++cnt;
return true;
}
for (auto e :adj[v])
if (e ^ par && dfs2(e , dst , v)) {
m1[v] = true;
val[v] = ++cnt;
return true;
}
}
void dfs3(int v, int par = -1) {
if (!m1[v]) val[v] = ++cnt;
for (auto e :adj[v])
if (e ^ par)
dfs3(e , v);
}
inline void init(int n , int m , int a[], int b[]) {
rep(i , 0 , m)
{ adj[a[i]].pb(i);
adj[b[i]].pb(i);
}
dfs0(0, a, b);
rep(i , 0 , n) adj[i].clear();
rep(i , 0 , m) if(m2[i]) {
adj[a[i]].pb(b[i]);
adj[b[i]].pb(a[i]);
}
lvl[0] = 1;
dfs1(0);
root = max_element(lvl , lvl + n) - lvl;
lvl[root] = 1;
dfs1(root);
len = *max_element(lvl , lvl + n);
return;
}
void Joi(int n, int m, int a[] , int b[], ll x , int t) {
init(n , m , a , b);
if (len >= 60) {
rep(i , 0 , n)
MessageBoard(i , (x >> (lvl[i] % 60)) & 1);
}
else {
int root2 = max_element(lvl , lvl + n) - lvl;
m1.reset();
dfs2(root , root2);
dfs3(root);
rep(i , 0 , n)
MessageBoard(i , (x >> (val[i] - 1)) & 1);
}
return;
}
#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back
constexpr int N = 1e4 + 10;
int root = -1, len = -1;
int lvl[N], val[N];
vi adj[N];
bitset<N << 1> m1, m2;
void dfs0(int v, int a[], int b[]) {
m1[v] = true;
for (auto e : adj[v]) {
int u = v ^ a[e] ^ b[e];
if (!m1[u]) {
m2[e] = true;
dfs0(u, a, b);
}
}
}
void dfs1(int v, int par = -1) {
for (auto e : adj[v])
if (par ^ e) {
lvl[e] = lvl[v] + 1;
dfs1(e , v);
}
}
int cnt;
bool dfs2(int v , int dst , int par = -1) {
if (v == dst) {
m1[v] = true;
val[v] = ++cnt;
return true;
}
for (auto e :adj[v])
if (e ^ par && dfs2(e , dst , v)) {
m1[v] = true;
val[v] = ++cnt;
return true;
}
}
void dfs3(int v, int par = -1) {
if (!m1[v]) val[v] = ++cnt;
for (auto e :adj[v])
if (e ^ par)
dfs3(e , v);
}
inline void init(int n , int m , int a[], int b[]) {
rep(i , 0 , m)
{ adj[a[i]].pb(i);
adj[b[i]].pb(i);
}
dfs0(0, a, b);
rep(i , 0 , n) adj[i].clear();
rep(i , 0 , m) if(m2[i]) {
adj[a[i]].pb(b[i]);
adj[b[i]].pb(a[i]);
}
lvl[0] = 1;
dfs1(0);
root = max_element(lvl , lvl + n) - lvl;
lvl[root] = 1;
dfs1(root);
len = *max_element(lvl , lvl + n);
return;
}
ll res = 0;
void dfs4(int v, int &p , int &me, int par = -1) {
res |= (1ll * me) << (val[v] - 1);
for (auto e : adj[v])
if (e ^ par && !m1[e] && val[e] <= 60) {
me = Move(e);
p = e;
dfs4(e , p , me , v);
}
for (auto e :adj[v])
if (e ^ par && m1[e] && val[e] <= 60) {
me = Move(e);
p = e;
dfs4(e , p , me , v);
}
if (!m1[v]) {
me = Move(par);
p = par;
}
}
ll Ioi(int n, int m, int a[], int b[], int p ,int me, int t) {
init(n , m , a , b);
if (len >= 60) {
m1.reset();
dfs2(p , root);
if (lvl[p] >= 60) {
rep(i , 0 , 60) {
res |= (1ll * me) << (lvl[p] % 60);
for (auto e : adj[p])
if (m1[e]) {
me = Move(e);
m1[p] = false;
p = e;
break;
}
}
}
else {
while(true) {
bool flag = false;
for (auto e : adj[p])
if (m1[e]) {
me = Move(e);
m1[p] = false;
flag = true;
p = e;
break;
}
if (!flag) break;
}
int root2 = max_element(lvl , lvl + n) - lvl;
dfs2(p , root2);
rep(i , 0 , 60) {
res |= (1ll * me) << (lvl[p] % 60);
for (auto e : adj[p])
if (m1[e]) {
me = Move(e);
m1[p] = false;
p = e;
break;
}
}
}
return res;
}
////////////////////////////////////////
int root2 = max_element(lvl , lvl + n) - lvl;
m1.reset();
dfs2(p ,root);
while(true) {
bool flag = false;
for (auto e : adj[p])
if (m1[e]) {
me = Move(e);
m1[p] = false;
flag = true;
p = e;
break;
}
if (!flag) break;
}
cnt = 0;
m1.reset();
dfs2(root , root2);
dfs3(root);
m1.reset();
dfs4(root, p , me);
return res;
}
Compilation message
Joi.cpp: In function 'bool dfs2(int, int, int)':
Joi.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
Ioi.cpp: In function 'bool dfs2(int, int, int)':
Ioi.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1280 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
4188 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1288 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1152 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1152 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1744 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1744 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1708 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1692 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1700 KB |
Output is correct |
| 9 |
Correct |
15 ms |
3904 KB |
Output is correct |
| 10 |
Correct |
15 ms |
4008 KB |
Output is correct |
| 11 |
Correct |
15 ms |
3900 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1408 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1152 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1288 KB |
Output is correct |
| 15 |
Correct |
4 ms |
1152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
4432 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
4376 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
