#include <bits/stdc++.h>
#include "Joi.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) {
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;
}
/*
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 && 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(root , root2);
dfs3(root);
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;
}
m1.reset();
dfs4(root, p , me);
return res;
}
*/
#include <bits/stdc++.h>
//#include "Joi.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) {
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;
}*/
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 && 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(root , root2);
dfs3(root);
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;
}
m1.reset();
dfs4(root, p , me);
return res;
}
Compilation message
Joi.cpp: In function 'bool dfs2(int, int, int)':
Joi.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
Ioi.cpp: In function 'bool dfs2(int, int, int)':
Ioi.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1292 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
4616 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1284 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
1292 KB |
Wrong Answer [7] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
4756 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
4776 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
