#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9;
const ll inf = 1e17;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi = 3.14159265359;
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 1e5;
#include "Joi.h"
/*int VAL[mxn];
void MessageBoard(int u, int val){
VAL[u] = val;
return;
}*/
int n, m;
vector<int> g[mxn];
int depth[mxn];
int mx_depth[mxn];
int parent[mxn];
void dfs(int u, int p){
parent[u] = p;
mx_depth[u] = depth[u];
for(auto e : g[u]){
if(e == p) continue;
depth[e] = depth[u]+1;
dfs(e, u);
mx_depth[u] = max(mx_depth[u], mx_depth[e]);
}
}
int pos;
ll res;
bool vis[mxn];
void dfs2(int u, int p){
if(pos < 60 && (res & (1 << pos))) MessageBoard(u, 1);
else MessageBoard(u, 0);
++pos;
for(auto e : g[u]){
if(e == p) continue;
dfs2(e, u);
}
}
void mark_tree(){
dfs(0, 0);
if(mx_depth[0] < 59){
dfs2(0, 0);
}
else{
fr(i, 0, n){
if(res&(1LL<<(depth[i]%60))) MessageBoard(i, 1);
else MessageBoard(i, 0);
}
}
}
int link[mxn];
int sz[mxn];
int cnt = 0;
int findx(int x){
while(x != link[x]) x = link[x];
return x;
}
void unite(int a, int b){
int uu = a, vv = b;
a = findx(a);
b = findx(b);
if(a == b) return;
g[uu].pb(vv);
g[vv].pb(uu);
++cnt;
if(sz[a] < sz[b]) swap(a, b);
link[b] = link[a];
sz[a] += sz[b];
}
int a[mxn], b[mxn];
void build_tree(){
fr(i, 0, n) link[i] = i, sz[i] = 1;
fr(i, 0, m){
unite(a[i], b[i]);
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
res = X;
n = N, m = M;
fr(i, 0, M) a[i] = A[i], b[i] = B[i];
build_tree();
mark_tree();
}
/*
int main(){
int N, M, X, T;
cin >> N >> M >> X;
int A[N], B[M];
fr(i, 0, M){
cin >> A[i] >> B[i];
}
Joi(N, M, A, B, X, 1);
fr(i, 0, n) cout<<VAL[i]<<',';
cout<<endl;
}
60 59 123
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
56 57
57 58
58 59
*/
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9;
const ll inf = 1e17;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi = 3.14159265359;
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 1e5;
#include "Ioi.h"
/*
int mark[60] = {1,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int Move(int u){
//cout<<u<<endl;
return mark[u];
}*/
vector<int> g[mxn];
int depth[mxn];
int mx_depth[mxn];
int parent[mxn];
void dfs(int u, int p){
parent[u] = p;
mx_depth[u] = depth[u];
for(auto e : g[u]){
if(e == p) continue;
depth[e] = depth[u]+1;
dfs(e, u);
mx_depth[u] = max(mx_depth[u], mx_depth[e]);
}
}
ll res;
ll pos;
void dfs2(int u, int p, ll val){
if(pos > 59) return;
res |= ((1LL<<pos)*val);
++pos;
if(pos > 59) return;
for(auto e : g[u]){
if(e == p) continue;
dfs2(e, u, (ll)Move(e));
if(pos > 59) return;
}
if(u != p) Move(p);
}
void edge_case(ll val){
dfs2(0, 0, val);
}
void solve_tree(int x, ll val){
dfs(0, 0);
while(depth[x] % 60 != 0){
val = (ll)Move(parent[x]);
x = parent[x];
}
if(mx_depth[x] < 59){
if(x == 0) edge_case(val);
else{
val = (ll)Move(parent[x]);
x = parent[x];
fr(i, 0, 60){
res |= ((1LL<<(59-i))*val);
if(x!=parent[x]) val = (ll)Move(parent[x]);
x = parent[x];
}
}
}
else{
fr(i, 0, 60){
cout<<val<<' ';
res |= ((1LL<<i)*val);
int id = -1;
for(auto u : g[x]){
if(u == parent[x]) continue;
if(mx_depth[x] == mx_depth[u]){
id = u;
break;
}
}
if(id == -1) break;
val = (ll)Move(id);
x = id;
}
}
}
int link[mxn];
int sz[mxn];
int findx(int x){
while(x != link[x]) x = link[x];
return x;
}
void unite(int a, int b){
int uu = a, vv = b;
a = findx(a);
b = findx(b);
if(a == b) return;
g[uu].pb(vv);
g[vv].pb(uu);
if(sz[a] < sz[b]) swap(a, b);
link[b] = link[a];
sz[a] += sz[b];
}
int n, m;
int a[mxn], b[mxn];
void build_tree(){
fr(i, 0, n) link[i] = i, sz[i] = 1;
fr(i, 0, m){
unite(a[i], b[i]);
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
n = N, m = M;
fr(i, 0, M) a[i] = A[i], b[i] = B[i];
build_tree();
solve_tree(P, V);
return res;
}/*
int main(){
int N, M, P, V;
cin >> N >> M >> P;
V = mark[P];
int A[N], B[M];
fr(i, 0, M){
cin >> A[i] >> B[i];
}
cout<<Ioi(N, M, A, B, P, V, 1);
}
60 59 5
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
56 57
57 58
58 59
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5512 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
8508 KB |
Do not print anything on standard output. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
5384 KB |
Do not print anything on standard output. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
8576 KB |
Do not print anything on standard output. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
8620 KB |
Do not print anything on standard output. |
| 2 |
Halted |
0 ms |
0 KB |
- |
