| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 638233 |
2022-09-05T04:46:57 Z |
tabr |
Werewolf (IOI18_werewolf) |
C++17 |
|
4000 ms |
82600 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
template <typename T>
struct forest {
struct edge {
int from;
int to;
T cost;
edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {}
};
int n;
vector<edge> edges;
vector<vector<int>> g;
vector<int> pv;
vector<int> pe;
vector<int> depth;
vector<int> root;
vector<int> sz;
vector<int> order;
vector<int> beg;
vector<int> end;
vector<T> dist;
forest(int _n) : n(_n) {
g = vector<vector<int>>(n);
init();
}
void init() {
pv = vector<int>(n, -1);
pe = vector<int>(n, -1);
depth = vector<int>(n, -1);
root = vector<int>(n, -1);
sz = vector<int>(n, 0);
order = vector<int>();
beg = vector<int>(n, -1);
end = vector<int>(n, -1);
dist = vector<T>(n, 0);
}
int add(int from, int to, T cost = 1) {
int id = (int) edges.size();
g[from].emplace_back(id);
g[to].emplace_back(id);
edges.emplace_back(from, to, cost);
return id;
}
void do_dfs(int v) {
beg[v] = (int) order.size();
order.emplace_back(v);
sz[v] = 1;
for (int id : g[v]) {
if (id == pe[v]) {
continue;
}
edge e = edges[id];
int to = e.from ^ e.to ^ v;
pv[to] = v;
pe[to] = id;
depth[to] = depth[v] + 1;
root[to] = (root[v] != -1 ? root[v] : to);
dist[to] = dist[v] + e.cost;
do_dfs(to);
sz[v] += sz[to];
}
end[v] = (int) order.size();
}
void dfs(int v) {
pv[v] = -1;
pe[v] = -1;
depth[v] = 0;
root[v] = v;
order.clear();
dist[v] = 0;
do_dfs(v);
}
void dfs_all() {
init();
for (int v = 0; v < n; v++) {
if (depth[v] == -1) {
dfs(v);
}
}
}
int h = -1;
vector<vector<int>> p;
inline void build_lca() {
int max_depth = *max_element(depth.begin(), depth.end());
h = 1;
while ((1 << h) <= max_depth) {
h++;
}
p = vector<vector<int>>(h, vector<int>(n));
p[0] = pv;
for (int i = 1; i < h; i++) {
for (int j = 0; j < n; j++) {
p[i][j] = (p[i - 1][j] == -1 ? -1 : p[i - 1][p[i - 1][j]]);
}
}
}
inline bool anc(int x, int y) { // return x is y's ancestor or not
return (beg[x] <= beg[y] && end[y] <= end[x]);
}
inline int go_up(int x, int up) {
assert(h != -1);
up = min(up, (1 << h) - 1);
for (int i = h - 1; i >= 0; i--) {
if (up & (1 << i)) {
x = p[i][x];
if (x == -1) {
break;
}
}
}
return x;
}
inline int lca(int x, int y) {
assert(h != -1);
if (anc(x, y)) {
return x;
}
if (anc(y, x)) {
return y;
}
for (int i = h - 1; i >= 0; i--) {
if (p[i][x] != -1 && !anc(p[i][x], y)) {
x = p[i][x];
}
}
return p[0][x];
}
inline T distance(int x, int y) {
return dist[x] + dist[y] - 2 * dist[lca(x, y)];
}
};
struct dsu {
vector<int> p;
vector<int> sz;
int n;
dsu(int _n) : n(_n) {
p = vector<int>(n);
iota(p.begin(), p.end(), 0);
sz = vector<int>(n, 1);
}
inline int get(int x) {
if (p[x] == x) {
return x;
} else {
return p[x] = get(p[x]);
}
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) {
return false;
}
p[x] = y;
sz[y] += sz[x];
return true;
}
inline bool same(int x, int y) {
return (get(x) == get(y));
}
inline int size(int x) {
return sz[get(x)];
}
inline bool root(int x) {
return (x == get(x));
}
};
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
int m = (int) x.size();
int q = (int) s.size();
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
g[x[i]].emplace_back(y[i]);
g[y[i]].emplace_back(x[i]);
}
forest<int> g0(n), g1(n);
dsu uf(n);
for (int i = 0; i < n; i++) {
for (int j : g[i]) {
if (i > j && !uf.same(i, j)) {
g0.add(i, uf.get(j));
debug(i, uf.get(j));
uf.unite(j, i);
}
}
}
g0.dfs(n - 1);
g0.build_lca();
uf = dsu(n);
for (int i = n - 1; i >= 0; i--) {
for (int j : g[i]) {
if (j > i && !uf.same(i, j)) {
g1.add(i, uf.get(j));
debug(i, uf.get(j));
uf.unite(j, i);
}
}
}
g1.dfs(0);
g1.build_lca();
vector<int> res(q);
for (int i = 0; i < q; i++) {
for (int j = l[i]; j <= r[i]; j++) {
if (g0.lca(j, e[i]) <= r[i] && g1.lca(j, s[i]) >= l[i]) {
res[i] = 1;
break;
}
}
}
return res;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
debug(check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2}, {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4}));
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
296 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
304 KB |
Output is correct |
| 7 |
Correct |
1 ms |
296 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
296 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
304 KB |
Output is correct |
| 7 |
Correct |
1 ms |
296 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
78 ms |
1652 KB |
Output is correct |
| 11 |
Correct |
123 ms |
1624 KB |
Output is correct |
| 12 |
Correct |
128 ms |
1492 KB |
Output is correct |
| 13 |
Correct |
48 ms |
1716 KB |
Output is correct |
| 14 |
Correct |
39 ms |
1764 KB |
Output is correct |
| 15 |
Correct |
422 ms |
1728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4014 ms |
82600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
296 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
304 KB |
Output is correct |
| 7 |
Correct |
1 ms |
296 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
78 ms |
1652 KB |
Output is correct |
| 11 |
Correct |
123 ms |
1624 KB |
Output is correct |
| 12 |
Correct |
128 ms |
1492 KB |
Output is correct |
| 13 |
Correct |
48 ms |
1716 KB |
Output is correct |
| 14 |
Correct |
39 ms |
1764 KB |
Output is correct |
| 15 |
Correct |
422 ms |
1728 KB |
Output is correct |
| 16 |
Execution timed out |
4014 ms |
82600 KB |
Time limit exceeded |
| 17 |
Halted |
0 ms |
0 KB |
- |
