| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 425732 |
2021-06-13T10:39:10 Z |
KoD |
Werewolf (IOI18_werewolf) |
C++17 |
|
525 ms |
136388 KB |
#include <bits/stdc++.h>
#include "werewolf.h"
template <class T> using Vec = std::vector<T>;
struct UnionFind {
Vec<int> par;
Vec<Vec<int>> children;
UnionFind(const int n) : par(n), children(n) {
std::iota(par.begin(), par.end(), 0);
}
int find(const int u) {
return par[u] == u ? u : par[u] = find(par[u]);
}
void absorb(int u, int v) {
u = find(u);
v = find(v);
if (u == v) {
return;
}
par[v] = u;
children[u].push_back(v);
}
std::pair<Vec<int>, Vec<std::pair<int, int>>> build() {
const int n = (int) par.size();
Vec<int> ord;
ord.reserve(n);
Vec<std::pair<int, int>> range(n);
int timer = 0;
auto dfs = [&](auto&& dfs, const int u) -> void {
range[u].first = timer++;
ord.push_back(u);
for (const auto v : children[u]) {
dfs(dfs, v);
}
range[u].second = timer;
};
dfs(dfs, n - 1);
return std::make_pair(std::move(ord), std::move(range));
}
};
struct Fenwick {
Vec<int> data;
Fenwick(const int n): data(n + 1) {}
void add(int i, const int x) {
i += 1;
while (i < (int) data.size()) {
data[i] += x;
i += i & -i;
}
}
int get(int i) const {
int x = 0;
while (i > 0) {
x += data[i];
i -= i & -i;
}
return x;
}
int fold(const int l, const int r) const {
return get(r) - get(l);
}
};
Vec<int> check_validity(int N, Vec<int> X, Vec<int> Y, Vec<int> S, Vec<int> E, Vec<int> L, Vec<int> R) {
const int M = (int) X.size();
const int Q = (int) S.size();
Vec<Vec<int>> graph(N);
for (int i = 0; i < M; ++i) {
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(Y[i]);
}
UnionFind asc(N), dsc(N);
Vec<Vec<int>> rqs(N), lqs(N);
for (int i = 0; i < Q; ++i) {
rqs[R[i]].push_back(i);
lqs[L[i]].push_back(i);
}
Vec<int> rvert(Q), lvert(Q);
for (int u = 0; u < N; ++u) {
for (const auto v : graph[u]) {
if (v < u) {
asc.absorb(u, v);
}
}
for (const auto q : rqs[u]) {
rvert[q] = asc.find(E[q]);
}
}
for (int u = N - 1; u >= 0; --u) {
for (const auto v : graph[u]) {
if (u < v) {
dsc.absorb(u, v);
}
}
for (const auto q : lqs[u]) {
lvert[q] = dsc.find(S[q]);
}
}
const auto [rord, rrange] = asc.build();
const auto [lord, lrange] = dsc.build();
Vec<int> linv(N);
for (int i = 0; i < N; ++i) {
linv[lord[i]] = i;
}
Vec<Vec<int>> sub(N), add(N);
for (int i = 0; i < Q; ++i) {
const auto [l, r] = rrange[rvert[i]];
sub[l].push_back(i);
add[r - 1].push_back(i);
}
Fenwick fen(N);
Vec<int> ret(Q);
for (int i = 0; i < N; ++i) {
for (const auto q : sub[i]) {
const auto [u, d] = lrange[lvert[q]];
ret[q] -= fen.fold(u, d);
}
fen.add(linv[rord[i]], 1);
for (const auto q : add[i]) {
const auto [u, d] = lrange[lvert[q]];
ret[q] += fen.fold(u, d);
}
}
for (auto& x : ret) {
if (x > 0) {
x = 1;
}
}
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
525 ms |
136388 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
