#include "Joi.h"
#include <bits/stdc++.h>
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
static const int N = 1e4+5;
static int par[N];
static int find(int x) { return par[x] = x == par[x] ? x : find(par[x]); }
static vector<pii> t[N];
static vector<int> g[N];
static int idx, pre[N], pos[N], deg[N];
static void dfs(int u, int p) {
pre[u] = idx++;
for(int v : g[u]) if(v != p) dfs(v, u);
}
static void extend_tree(int u, int p) {
if(!t[u].empty()) return;
int leaf;
vector<pii> tree = t[p];
for(pii e : tree) ++deg[e.x], ++deg[e.y];
for(pii e : tree) {
int a, b; tie(a, b) = e;
if(deg[a] == 1 && a != p) { leaf = a; break; }
if(deg[b] == 1 && b != p) { leaf = b; break; }
}
pos[u] = pos[leaf];
for(pii e : tree) {
--deg[e.x], --deg[e.y];
if(e.x == leaf || e.y == leaf) continue;
t[u].emplace_back(e);
}
t[u].emplace_back(u, p);
for(int v : g[u]) if(v != p) extend_tree(v, u);
}
static void solve(int n, int m, int A[], int B[]) {
iota(par, par+N, 0);
vector<pii> E, ret, init;
for(int i = 0; i < m; i++) E.emplace_back(A[i], B[i]);
sort(E.begin(), E.end());
for(pii e : E) {
int a, b; tie(a, b) = e;
if(find(a) != find(b)) {
par[find(a)] = find(b);
g[a].emplace_back(b), g[b].emplace_back(a);
ret.emplace_back(a, b);
}
}
dfs(0, 0);
for(pii e : ret) if(pre[e.x] < 60 && pre[e.y] < 60) init.emplace_back(e);
for(int i = 0; i < n; i++) if(pre[i] < 60) {
pos[i] = pre[i];
t[i] = init;
}
for(int i = 0; i < n; i++) if(pre[i] < 60) for(int v : g[i]) extend_tree(v, i);
}
void Joi(int n, int m, int A[], int B[], long X, int T) {
solve(n, m, A, B);
for(int i = 0; i < n; i++) MessageBoard(i, X >> pos[i] & 1);
}
#include "Ioi.h"
#include <bits/stdc++.h>
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
static const int N = 1e4+5;
static int par[N];
static int find(int x) { return par[x] = x == par[x] ? x : find(par[x]); }
static vector<pii> t[N];
static vector<int> g[N];
static int idx, pre[N], pos[N], deg[N];
static void dfs(int u, int p) {
pre[u] = idx++;
for(int v : g[u]) if(v != p) dfs(v, u);
}
static void extend_tree(int u, int p) {
if(!t[u].empty()) return;
int leaf;
vector<pii> tree = t[p];
for(pii e : tree) ++deg[e.x], ++deg[e.y];
for(pii e : tree) {
int a, b; tie(a, b) = e;
if(deg[a] == 1 && a != p) { leaf = a; break; }
if(deg[b] == 1 && b != p) { leaf = b; break; }
}
pos[u] = pos[leaf];
for(pii e : tree) {
--deg[e.x], --deg[e.y];
if(e.x == leaf || e.y == leaf) continue;
t[u].emplace_back(e);
}
t[u].emplace_back(u, p);
for(int v : g[u]) if(v != p) extend_tree(v, u);
}
static void solve(int n, int m, int A[], int B[]) {
iota(par, par+N, 0);
vector<pii> E, ret, init;
for(int i = 0; i < m; i++) E.emplace_back(A[i], B[i]);
sort(E.begin(), E.end());
for(pii e : E) {
int a, b; tie(a, b) = e;
if(find(a) != find(b)) {
par[find(a)] = find(b);
g[a].emplace_back(b), g[b].emplace_back(a);
ret.emplace_back(a, b);
}
}
dfs(0, 0);
for(pii e : ret) if(pre[e.x] < 60 && pre[e.y] < 60) init.emplace_back(e);
for(int i = 0; i < n; i++) if(pre[i] < 60) {
pos[i] = pre[i];
t[i] = init;
}
for(int i = 0; i < n; i++) if(pre[i] < 60) for(int v : g[i]) extend_tree(v, i);
}
static long ans;
static void get_ans(int u, int p) {
for(int v : g[u]) if(v != p) {
int nex = Move(v);
if(nex) ans += 1ll << pos[v];
get_ans(v, u);
Move(u);
}
}
long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
solve(n, m, A, B);
for(int i = 0; i < n; i++) g[i].clear();
for(pii e : t[P]) g[e.x].emplace_back(e.y), g[e.y].emplace_back(e.x);
if(V) ans += 1ll << pos[P];
get_ans(P, P);
return ans;
}
Compilation message
Joi.cpp: In function 'void extend_tree(int, int)':
Joi.cpp:37:22: warning: 'leaf' may be used uninitialized in this function [-Wmaybe-uninitialized]
pos[u] = pos[leaf];
~~~~~~~~^
Ioi.cpp: In function 'void extend_tree(int, int)':
Ioi.cpp:37:22: warning: 'leaf' may be used uninitialized in this function [-Wmaybe-uninitialized]
pos[u] = pos[leaf];
~~~~~~~~^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
1792 KB |
Output is correct |
2 |
Correct |
7 ms |
2172 KB |
Output is correct |
3 |
Correct |
8 ms |
2212 KB |
Output is correct |
4 |
Correct |
8 ms |
1956 KB |
Output is correct |
5 |
Correct |
5 ms |
1920 KB |
Output is correct |
6 |
Correct |
6 ms |
2056 KB |
Output is correct |
7 |
Correct |
7 ms |
2384 KB |
Output is correct |
8 |
Correct |
6 ms |
2180 KB |
Output is correct |
9 |
Correct |
7 ms |
2260 KB |
Output is correct |
10 |
Correct |
6 ms |
2056 KB |
Output is correct |
11 |
Correct |
10 ms |
2096 KB |
Output is correct |
12 |
Correct |
3 ms |
1928 KB |
Output is correct |
13 |
Correct |
6 ms |
2188 KB |
Output is correct |
14 |
Correct |
6 ms |
2304 KB |
Output is correct |
15 |
Correct |
6 ms |
2052 KB |
Output is correct |
16 |
Correct |
7 ms |
2216 KB |
Output is correct |
17 |
Correct |
6 ms |
2180 KB |
Output is correct |
18 |
Correct |
7 ms |
2060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
80 ms |
14968 KB |
Output is correct |
2 |
Correct |
71 ms |
14972 KB |
Output is correct |
3 |
Correct |
77 ms |
14928 KB |
Output is correct |
4 |
Correct |
77 ms |
14028 KB |
Output is correct |
5 |
Correct |
79 ms |
19080 KB |
Output is correct |
6 |
Correct |
68 ms |
17452 KB |
Output is correct |
7 |
Correct |
82 ms |
17356 KB |
Output is correct |
8 |
Correct |
71 ms |
18508 KB |
Output is correct |
9 |
Correct |
86 ms |
18428 KB |
Output is correct |
10 |
Correct |
50 ms |
14352 KB |
Output is correct |
11 |
Correct |
63 ms |
14260 KB |
Output is correct |
12 |
Correct |
66 ms |
12932 KB |
Output is correct |
13 |
Correct |
58 ms |
12852 KB |
Output is correct |
14 |
Correct |
66 ms |
13564 KB |
Output is correct |
15 |
Correct |
55 ms |
14064 KB |
Output is correct |
16 |
Correct |
66 ms |
13868 KB |
Output is correct |
17 |
Correct |
63 ms |
13996 KB |
Output is correct |
18 |
Correct |
57 ms |
14004 KB |
Output is correct |
19 |
Correct |
79 ms |
13996 KB |
Output is correct |
20 |
Correct |
54 ms |
19440 KB |
Output is correct |
21 |
Correct |
78 ms |
19116 KB |
Output is correct |
22 |
Correct |
70 ms |
16692 KB |
Output is correct |
23 |
Correct |
63 ms |
18228 KB |
Output is correct |
24 |
Correct |
68 ms |
17104 KB |
Output is correct |
25 |
Correct |
67 ms |
17708 KB |
Output is correct |
26 |
Correct |
68 ms |
18220 KB |
Output is correct |
27 |
Correct |
76 ms |
18352 KB |
Output is correct |
28 |
Correct |
75 ms |
18612 KB |
Output is correct |
29 |
Correct |
68 ms |
16572 KB |
Output is correct |
30 |
Correct |
67 ms |
17064 KB |
Output is correct |
31 |
Correct |
6 ms |
1948 KB |
Output is correct |
32 |
Correct |
6 ms |
2184 KB |
Output is correct |
33 |
Correct |
7 ms |
2060 KB |
Output is correct |
34 |
Correct |
6 ms |
2184 KB |
Output is correct |
35 |
Correct |
6 ms |
1668 KB |
Output is correct |
36 |
Correct |
7 ms |
1920 KB |
Output is correct |
37 |
Correct |
5 ms |
1988 KB |
Output is correct |
38 |
Correct |
5 ms |
1876 KB |
Output is correct |
39 |
Correct |
6 ms |
1792 KB |
Output is correct |
40 |
Correct |
7 ms |
1792 KB |
Output is correct |
41 |
Correct |
6 ms |
1920 KB |
Output is correct |
42 |
Correct |
6 ms |
1920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
1920 KB |
Output is correct |
2 |
Correct |
6 ms |
2048 KB |
Output is correct |
3 |
Correct |
6 ms |
1792 KB |
Output is correct |
4 |
Correct |
14 ms |
5452 KB |
Output is correct |
5 |
Correct |
19 ms |
5376 KB |
Output is correct |
6 |
Correct |
15 ms |
5460 KB |
Output is correct |
7 |
Correct |
17 ms |
5404 KB |
Output is correct |
8 |
Correct |
14 ms |
5412 KB |
Output is correct |
9 |
Correct |
54 ms |
24668 KB |
Output is correct |
10 |
Correct |
57 ms |
24644 KB |
Output is correct |
11 |
Correct |
50 ms |
24640 KB |
Output is correct |
12 |
Correct |
6 ms |
1928 KB |
Output is correct |
13 |
Correct |
4 ms |
1792 KB |
Output is correct |
14 |
Correct |
6 ms |
1800 KB |
Output is correct |
15 |
Correct |
6 ms |
1972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
72 ms |
14988 KB |
Output is correct |
2 |
Correct |
74 ms |
14716 KB |
Output is correct |
3 |
Correct |
75 ms |
14976 KB |
Output is correct |
4 |
Correct |
66 ms |
13880 KB |
Output is correct |
5 |
Correct |
72 ms |
21916 KB |
Output is correct |
6 |
Correct |
71 ms |
18532 KB |
Output is correct |
7 |
Correct |
79 ms |
18156 KB |
Output is correct |
8 |
Correct |
69 ms |
16332 KB |
Output is correct |
9 |
Correct |
59 ms |
17100 KB |
Output is correct |
10 |
Correct |
53 ms |
14156 KB |
Output is correct |
11 |
Correct |
55 ms |
14168 KB |
Output is correct |
12 |
Correct |
56 ms |
12964 KB |
Output is correct |
13 |
Correct |
57 ms |
13024 KB |
Output is correct |
14 |
Correct |
71 ms |
13380 KB |
Output is correct |
15 |
Correct |
55 ms |
14024 KB |
Output is correct |
16 |
Correct |
65 ms |
14044 KB |
Output is correct |
17 |
Correct |
59 ms |
14072 KB |
Output is correct |
18 |
Correct |
66 ms |
14060 KB |
Output is correct |
19 |
Correct |
56 ms |
13904 KB |
Output is correct |
20 |
Correct |
56 ms |
19432 KB |
Output is correct |
21 |
Correct |
66 ms |
19408 KB |
Output is correct |
22 |
Correct |
83 ms |
18032 KB |
Output is correct |
23 |
Correct |
60 ms |
17648 KB |
Output is correct |
24 |
Correct |
71 ms |
17396 KB |
Output is correct |
25 |
Correct |
82 ms |
18404 KB |
Output is correct |
26 |
Correct |
66 ms |
18084 KB |
Output is correct |
27 |
Correct |
80 ms |
19032 KB |
Output is correct |
28 |
Correct |
78 ms |
17048 KB |
Output is correct |
29 |
Correct |
78 ms |
16412 KB |
Output is correct |
30 |
Correct |
62 ms |
17388 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
14992 KB |
Output is correct |
2 |
Correct |
107 ms |
15124 KB |
Output is correct |
3 |
Correct |
87 ms |
14980 KB |
Output is correct |
4 |
Correct |
57 ms |
14088 KB |
Output is correct |
5 |
Correct |
88 ms |
23020 KB |
Output is correct |
6 |
Correct |
68 ms |
17152 KB |
Output is correct |
7 |
Correct |
72 ms |
16928 KB |
Output is correct |
8 |
Correct |
72 ms |
18528 KB |
Output is correct |
9 |
Correct |
69 ms |
17752 KB |
Output is correct |
10 |
Correct |
52 ms |
14332 KB |
Output is correct |
11 |
Correct |
56 ms |
14320 KB |
Output is correct |
12 |
Correct |
56 ms |
13000 KB |
Output is correct |
13 |
Correct |
59 ms |
13024 KB |
Output is correct |
14 |
Correct |
55 ms |
13716 KB |
Output is correct |
15 |
Correct |
64 ms |
14200 KB |
Output is correct |
16 |
Correct |
72 ms |
13956 KB |
Output is correct |
17 |
Correct |
58 ms |
14300 KB |
Output is correct |
18 |
Correct |
67 ms |
14112 KB |
Output is correct |
19 |
Correct |
59 ms |
14300 KB |
Output is correct |
20 |
Correct |
50 ms |
19336 KB |
Output is correct |
21 |
Correct |
57 ms |
19304 KB |
Output is correct |
22 |
Correct |
63 ms |
17800 KB |
Output is correct |
23 |
Correct |
61 ms |
17416 KB |
Output is correct |
24 |
Correct |
71 ms |
17512 KB |
Output is correct |
25 |
Correct |
82 ms |
17656 KB |
Output is correct |
26 |
Correct |
79 ms |
16876 KB |
Output is correct |
27 |
Correct |
81 ms |
19112 KB |
Output is correct |
28 |
Correct |
77 ms |
19440 KB |
Output is correct |
29 |
Correct |
63 ms |
17788 KB |
Output is correct |
30 |
Correct |
78 ms |
17828 KB |
Output is correct |
31 |
Correct |
6 ms |
2176 KB |
Output is correct |
32 |
Correct |
7 ms |
2148 KB |
Output is correct |
33 |
Correct |
8 ms |
2224 KB |
Output is correct |
34 |
Correct |
6 ms |
2180 KB |
Output is correct |
35 |
Correct |
6 ms |
1940 KB |
Output is correct |
36 |
Correct |
5 ms |
1824 KB |
Output is correct |
37 |
Correct |
6 ms |
1960 KB |
Output is correct |
38 |
Correct |
6 ms |
1928 KB |
Output is correct |
39 |
Correct |
6 ms |
1920 KB |
Output is correct |
40 |
Correct |
12 ms |
1928 KB |
Output is correct |
41 |
Correct |
7 ms |
1928 KB |
Output is correct |
42 |
Correct |
8 ms |
1920 KB |
Output is correct |