#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
void Joi(int N, int M, int A[], int B[], long long X, int T) {
struct DSU {
vector<int> p;
DSU() = default;
DSU(int n) : p(n) {
iota(p.begin(), p.end(), 0);
}
int leader(int x) {
while (x != p[x]) x = p[x] = p[p[x]];
return x;
}
bool unite(int x, int y) {
x = leader(x), y = leader(y);
if (p[y] == x) {
return false;
} else {
return p[y] = x, true;
}
}
};
mt19937 rnd(228);
vector<pair<int, int>> edges(M);
for (int i = 0; i < M; ++i) {
edges[i] = {A[i], B[i]};
}
shuffle(edges.begin(), edges.end(), rnd);
vector<int> tin(N), par(N, -1);
vector<vector<int>> g(N), adj(N);
DSU d(N);
for (int i = 0; i < M; ++i) {
auto [a, b] = edges[i];
if (d.unite(a, b)) {
g[a].push_back(b);
g[b].push_back(a);
}
}
int timer = 0;
function<void(int)> dfs = [&](int v) {
tin[v] = timer++;
sort(g[v].begin(), g[v].end());
for (int to : g[v]) {
if (to != par[v]) {
par[to] = v;
adj[v].push_back(to);
dfs(to);
}
}
};
dfs(0);
for (int i = 0; i < N; ++i) {
MessageBoard(i, X >> (tin[i] % 60) & 1);
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
struct DSU {
vector<int> p;
DSU() = default;
DSU(int n) : p(n) {
iota(p.begin(), p.end(), 0);
}
int leader(int x) {
while (x != p[x]) x = p[x] = p[p[x]];
return x;
}
bool unite(int x, int y) {
x = leader(x), y = leader(y);
if (p[y] == x) {
return false;
} else {
return p[y] = x, true;
}
}
};
mt19937 rnd(228);
vector<pair<int, int>> edges(M);
for (int i = 0; i < M; ++i) {
edges[i] = {A[i], B[i]};
}
shuffle(edges.begin(), edges.end(), rnd);
vector<int> tin(N), par(N, -1), tout(N);
vector<vector<int>> g(N), adj(N);
DSU d(N);
for (int i = 0; i < M; ++i) {
auto [a, b] = edges[i];
if (d.unite(a, b)) {
g[a].push_back(b);
g[b].push_back(a);
}
}
int timer = 0;
function<void(int)> dfs = [&](int v) {
tin[v] = timer++;
sort(g[v].begin(), g[v].end());
for (int to: g[v]) {
if (to != par[v]) {
par[to] = v;
adj[v].push_back(to);
dfs(to);
}
}
tout[v] = timer++;
};
dfs(0);
int LOG = 60;
vector<bool> used(N);
vector<int> ans(LOG, -1);
ans[tin[P] % LOG] = V;
vector<int> last(N, -1);
int x = P;
auto any = [&](int l, int r) {
if (l >= r) {
return (find(ans.begin(), ans.begin() + r, -1) != (ans.begin() + r))
|| (find(ans.begin() + l, ans.end(), -1) != ans.end());
}
return find(ans.begin() + l, ans.begin() + r, -1) != (ans.begin() + r);
};
while (any(0, LOG)) {
used[x] = true;
auto it = upper_bound(adj[x].begin(), adj[x].end(), last[x]);
if (it == adj[x].end()) {
it = adj[x].begin();
}
if (adj[x].empty() || used[*it]) {
last[par[x]] = x;
x = par[x];
assert(x != -1);
ans[tin[x] % LOG] = Move(x);
} else {
last[x] = *it;
int to = *it;
used[to] = true;
if (any(tin[to] % 60, tout[to] % 60)) {
x = *it;
ans[tin[x] % LOG] = Move(x);
}
}
}
ll X = 0;
for (int i = 0; i < LOG; ++i) {
assert(ans[i] != -1);
X += ans[i] * (1LL << i);
}
return X;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
776 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
4200 KB |
Wrong Answer [7] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
780 KB |
Output is correct |
2 |
Correct |
1 ms |
776 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
3 ms |
1572 KB |
Output is correct |
5 |
Correct |
3 ms |
1564 KB |
Output is correct |
6 |
Correct |
3 ms |
1440 KB |
Output is correct |
7 |
Correct |
3 ms |
1572 KB |
Output is correct |
8 |
Correct |
3 ms |
1440 KB |
Output is correct |
9 |
Correct |
16 ms |
5716 KB |
Output is correct |
10 |
Correct |
17 ms |
5960 KB |
Output is correct |
11 |
Correct |
14 ms |
5668 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
2 ms |
640 KB |
Output is correct |
14 |
Correct |
1 ms |
512 KB |
Output is correct |
15 |
Correct |
0 ms |
508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
4136 KB |
Wrong Answer [7] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
24 ms |
4168 KB |
Wrong Answer [7] |
2 |
Halted |
0 ms |
0 KB |
- |