#include "Joi.h"
#include "bits/stdc++.h"
using namespace std;
vector <int> g[10010];
vector <int> t[10010];
bool vis[10010];
const int bit = 60; // 60;
int nodes;
int par[10010];
int ans[10010];
void dfs(int x) {
vis[x] = true;
for(auto i : g[x]) {
if(vis[i] == false) {
t[x].push_back(i);
par[i] = x;
dfs(i);
}
}
}
int cnt;
bool good[10010];
void get_first(int x) {
if(cnt >= bit) {
return ;
}
good[x] = true;
++cnt;
for(auto i : t[x]) {
get_first(i);
}
}
int degree(int x) {
int cnt = 0;
for(auto i : t[x]) {
cnt += good[i];
}
if(x != 0) {
cnt += good[par[x]];
}
return cnt;
}
void solve(int x) {
int leaf = -1;
for(int i = 0; i < nodes; i++) {
if(good[i] && par[x] != i) {
if(degree(i) == 1) {
leaf = i;
break;
}
}
}
good[x] = true;
good[leaf] = false;
ans[x] = ans[leaf];
for(auto i : t[x]) {
solve(i);
}
good[x] = false;
good[leaf] = true;
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
for(int i = 0; i < N; i++) {
g[i].clear();
t[i].clear();
good[i] = false;
vis[i] = false;
ans[i] = -1;
}
nodes = N;
for(int i = 0; i < M; i++) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
for(int i = 0; i < N; i++) {
sort(g[i].begin(), g[i].end());
}
dfs(0);
get_first(0);
int cur = 0;
for(int i = 0; i < N; i++) {
if(good[i]) {
ans[i] = cur++;
}
}
for(int i = 0; i < N; i++) {
if(good[i] == false && good[par[i]] == true) {
solve(i);
}
}
for(int i = 0; i < N; i++) {
int val = (X >> ans[i]) & 1;
MessageBoard(i, val);
}
return ;
}
#include "Ioi.h"
#include "bits/stdc++.h"
using namespace std;
#define g G
#define t TT
#define vis Vis
#define bit Bit
#define nodes Nodes
#define par Par
#define ans Ans
#define dfs Dfs
#define good Good
#define get_first Get_first
#define degree Degree
#define cnt Cnt
#define solveNow SolveNow
#define solve Solve
vector <int> g[10010];
vector <int> t[10010];
vector <int> Tree[10010];
bool vis[10010];
const int bit = 60; // 60;
int nodes;
int par[10010];
int ans[10010];
void dfs(int x) {
vis[x] = true;
for(auto i : g[x]) {
if(vis[i] == false) {
t[x].push_back(i);
Tree[x].push_back(i);
Tree[i].push_back(x);
par[i] = x;
dfs(i);
}
}
}
int cnt;
bool good[10010];
void get_first(int x) {
if(cnt >= bit) {
return ;
}
good[x] = true;
++cnt;
for(auto i : t[x]) {
get_first(i);
}
}
int degree(int x) {
int cnt = 0;
for(auto i : t[x]) {
cnt += good[i];
}
if(x != 0) {
cnt += good[par[x]];
}
return cnt;
}
int src;
long long Res;
int init;
set <int> s;
void shit(int x, int parent, int val) {
if(val) {
Res |= (1LL << ans[x]);
}
for(auto i : Tree[x]) {
if(good[i] == true && i != parent) {
shit(i, x, Move(i));
Move(x);
}
}
}
void solveNow() {
Res = 0;
shit(src, -1, init);
}
void solve(int x) {
int leaf = 0;
for(int i = 0; i < nodes; i++) {
if(good[i] && par[x] != i) {
if(degree(i) == 1) {
leaf = i;
break;
}
}
}
good[x] = true;
good[leaf] = false;
ans[x] = ans[leaf];
if(x == src) {
solveNow();
}
for(auto i : t[x]) {
solve(i);
}
good[x] = false;
good[leaf] = true;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
for(int i = 0; i < N; i++) {
g[i].clear();
t[i].clear();
Tree[i].clear();
good[i] = false;
vis[i] = false;
ans[i] = -1;
}
nodes = N;
for(int i = 0; i < M; i++) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
for(int i = 0; i < N; i++) {
sort(g[i].begin(), g[i].end());
}
src = P;
init = V;
dfs(0);
get_first(0);
int cur = 0;
for(int i = 0; i < N; i++) {
if(good[i]) {
ans[i] = cur++;
}
}
if(good[src] == true) {
solveNow();
}
for(int i = 0; i < N; i++) {
if(good[i] == false && good[par[i]] == true) {
solve(i);
}
}
return Res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
6124 KB |
Output is correct |
2 |
Correct |
0 ms |
6124 KB |
Output is correct |
3 |
Correct |
0 ms |
6124 KB |
Output is correct |
4 |
Correct |
0 ms |
6124 KB |
Output is correct |
5 |
Correct |
0 ms |
6124 KB |
Output is correct |
6 |
Correct |
0 ms |
6124 KB |
Output is correct |
7 |
Correct |
0 ms |
6124 KB |
Output is correct |
8 |
Correct |
0 ms |
6124 KB |
Output is correct |
9 |
Correct |
0 ms |
6124 KB |
Output is correct |
10 |
Correct |
0 ms |
6124 KB |
Output is correct |
11 |
Correct |
0 ms |
6388 KB |
Output is correct |
12 |
Correct |
0 ms |
6124 KB |
Output is correct |
13 |
Correct |
0 ms |
6124 KB |
Output is correct |
14 |
Correct |
0 ms |
6124 KB |
Output is correct |
15 |
Correct |
0 ms |
6124 KB |
Output is correct |
16 |
Correct |
0 ms |
6124 KB |
Output is correct |
17 |
Correct |
0 ms |
6124 KB |
Output is correct |
18 |
Correct |
0 ms |
6124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
122 ms |
8212 KB |
Output is correct |
2 |
Correct |
139 ms |
8220 KB |
Output is correct |
3 |
Correct |
119 ms |
8204 KB |
Output is correct |
4 |
Correct |
78 ms |
7444 KB |
Output is correct |
5 |
Correct |
126 ms |
8028 KB |
Output is correct |
6 |
Correct |
125 ms |
7584 KB |
Output is correct |
7 |
Correct |
125 ms |
7596 KB |
Output is correct |
8 |
Correct |
119 ms |
7680 KB |
Output is correct |
9 |
Correct |
122 ms |
7692 KB |
Output is correct |
10 |
Correct |
15 ms |
7476 KB |
Output is correct |
11 |
Correct |
15 ms |
7476 KB |
Output is correct |
12 |
Correct |
98 ms |
7312 KB |
Output is correct |
13 |
Correct |
84 ms |
7312 KB |
Output is correct |
14 |
Correct |
138 ms |
7444 KB |
Output is correct |
15 |
Correct |
75 ms |
7708 KB |
Output is correct |
16 |
Correct |
59 ms |
7708 KB |
Output is correct |
17 |
Correct |
92 ms |
7444 KB |
Output is correct |
18 |
Correct |
96 ms |
7444 KB |
Output is correct |
19 |
Correct |
84 ms |
7444 KB |
Output is correct |
20 |
Correct |
108 ms |
7816 KB |
Output is correct |
21 |
Correct |
102 ms |
7812 KB |
Output is correct |
22 |
Correct |
142 ms |
7512 KB |
Output is correct |
23 |
Correct |
129 ms |
7684 KB |
Output is correct |
24 |
Correct |
125 ms |
7560 KB |
Output is correct |
25 |
Correct |
129 ms |
7636 KB |
Output is correct |
26 |
Correct |
119 ms |
7688 KB |
Output is correct |
27 |
Correct |
132 ms |
7700 KB |
Output is correct |
28 |
Correct |
129 ms |
7724 KB |
Output is correct |
29 |
Correct |
122 ms |
7480 KB |
Output is correct |
30 |
Correct |
105 ms |
7492 KB |
Output is correct |
31 |
Correct |
0 ms |
6124 KB |
Output is correct |
32 |
Correct |
0 ms |
6124 KB |
Output is correct |
33 |
Correct |
0 ms |
6124 KB |
Output is correct |
34 |
Correct |
0 ms |
6124 KB |
Output is correct |
35 |
Correct |
0 ms |
6124 KB |
Output is correct |
36 |
Correct |
0 ms |
6124 KB |
Output is correct |
37 |
Correct |
0 ms |
6124 KB |
Output is correct |
38 |
Correct |
0 ms |
6124 KB |
Output is correct |
39 |
Correct |
0 ms |
6124 KB |
Output is correct |
40 |
Correct |
0 ms |
6124 KB |
Output is correct |
41 |
Correct |
0 ms |
6124 KB |
Output is correct |
42 |
Correct |
0 ms |
6124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
6124 KB |
Output is correct |
2 |
Correct |
0 ms |
6124 KB |
Output is correct |
3 |
Correct |
0 ms |
6124 KB |
Output is correct |
4 |
Correct |
3 ms |
6388 KB |
Output is correct |
5 |
Correct |
3 ms |
6388 KB |
Output is correct |
6 |
Correct |
0 ms |
6388 KB |
Output is correct |
7 |
Correct |
6 ms |
6388 KB |
Output is correct |
8 |
Correct |
6 ms |
6388 KB |
Output is correct |
9 |
Correct |
102 ms |
8696 KB |
Output is correct |
10 |
Correct |
102 ms |
8696 KB |
Output is correct |
11 |
Correct |
115 ms |
8692 KB |
Output is correct |
12 |
Correct |
0 ms |
6124 KB |
Output is correct |
13 |
Correct |
0 ms |
6124 KB |
Output is correct |
14 |
Correct |
0 ms |
6124 KB |
Output is correct |
15 |
Correct |
0 ms |
6124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
135 ms |
8204 KB |
Output is correct |
2 |
Correct |
155 ms |
8204 KB |
Output is correct |
3 |
Correct |
129 ms |
8208 KB |
Output is correct |
4 |
Correct |
65 ms |
7444 KB |
Output is correct |
5 |
Correct |
132 ms |
8344 KB |
Output is correct |
6 |
Correct |
138 ms |
7700 KB |
Output is correct |
7 |
Correct |
132 ms |
7672 KB |
Output is correct |
8 |
Correct |
132 ms |
7452 KB |
Output is correct |
9 |
Correct |
146 ms |
7544 KB |
Output is correct |
10 |
Correct |
12 ms |
7476 KB |
Output is correct |
11 |
Correct |
19 ms |
7476 KB |
Output is correct |
12 |
Correct |
92 ms |
7312 KB |
Output is correct |
13 |
Correct |
84 ms |
7312 KB |
Output is correct |
14 |
Correct |
112 ms |
7444 KB |
Output is correct |
15 |
Correct |
81 ms |
7708 KB |
Output is correct |
16 |
Correct |
81 ms |
7708 KB |
Output is correct |
17 |
Correct |
59 ms |
7444 KB |
Output is correct |
18 |
Correct |
72 ms |
7444 KB |
Output is correct |
19 |
Correct |
75 ms |
7444 KB |
Output is correct |
20 |
Correct |
119 ms |
7824 KB |
Output is correct |
21 |
Correct |
102 ms |
7812 KB |
Output is correct |
22 |
Correct |
132 ms |
7656 KB |
Output is correct |
23 |
Correct |
139 ms |
7604 KB |
Output is correct |
24 |
Correct |
132 ms |
7596 KB |
Output is correct |
25 |
Correct |
128 ms |
7692 KB |
Output is correct |
26 |
Correct |
122 ms |
7664 KB |
Output is correct |
27 |
Correct |
125 ms |
7776 KB |
Output is correct |
28 |
Correct |
125 ms |
7540 KB |
Output is correct |
29 |
Correct |
102 ms |
7464 KB |
Output is correct |
30 |
Correct |
115 ms |
7520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
8196 KB |
Output is correct |
2 |
Correct |
146 ms |
8212 KB |
Output is correct |
3 |
Correct |
142 ms |
8200 KB |
Output is correct |
4 |
Correct |
95 ms |
7444 KB |
Output is correct |
5 |
Correct |
139 ms |
8492 KB |
Output is correct |
6 |
Correct |
149 ms |
7556 KB |
Output is correct |
7 |
Correct |
135 ms |
7524 KB |
Output is correct |
8 |
Correct |
128 ms |
7696 KB |
Output is correct |
9 |
Correct |
114 ms |
7620 KB |
Output is correct |
10 |
Correct |
3 ms |
7476 KB |
Output is correct |
11 |
Correct |
22 ms |
7476 KB |
Output is correct |
12 |
Correct |
102 ms |
7312 KB |
Output is correct |
13 |
Correct |
92 ms |
7312 KB |
Output is correct |
14 |
Correct |
125 ms |
7444 KB |
Output is correct |
15 |
Correct |
78 ms |
7708 KB |
Output is correct |
16 |
Correct |
96 ms |
7708 KB |
Output is correct |
17 |
Correct |
76 ms |
7444 KB |
Output is correct |
18 |
Correct |
109 ms |
7444 KB |
Output is correct |
19 |
Correct |
75 ms |
7444 KB |
Output is correct |
20 |
Correct |
106 ms |
7820 KB |
Output is correct |
21 |
Correct |
95 ms |
7812 KB |
Output is correct |
22 |
Correct |
132 ms |
7640 KB |
Output is correct |
23 |
Correct |
138 ms |
7576 KB |
Output is correct |
24 |
Correct |
139 ms |
7584 KB |
Output is correct |
25 |
Correct |
129 ms |
7608 KB |
Output is correct |
26 |
Correct |
139 ms |
7516 KB |
Output is correct |
27 |
Correct |
122 ms |
7780 KB |
Output is correct |
28 |
Correct |
139 ms |
7788 KB |
Output is correct |
29 |
Correct |
106 ms |
7608 KB |
Output is correct |
30 |
Correct |
114 ms |
7556 KB |
Output is correct |
31 |
Correct |
0 ms |
6124 KB |
Output is correct |
32 |
Correct |
0 ms |
6124 KB |
Output is correct |
33 |
Correct |
0 ms |
6124 KB |
Output is correct |
34 |
Correct |
0 ms |
6124 KB |
Output is correct |
35 |
Correct |
0 ms |
6124 KB |
Output is correct |
36 |
Correct |
0 ms |
6124 KB |
Output is correct |
37 |
Correct |
0 ms |
6124 KB |
Output is correct |
38 |
Correct |
0 ms |
6124 KB |
Output is correct |
39 |
Correct |
0 ms |
6124 KB |
Output is correct |
40 |
Correct |
0 ms |
6124 KB |
Output is correct |
41 |
Correct |
0 ms |
6124 KB |
Output is correct |
42 |
Correct |
0 ms |
6124 KB |
Output is correct |