| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 815393 |
2023-08-08T14:39:52 Z |
erray |
Werewolf (IOI18_werewolf) |
C++17 |
|
732 ms |
64044 KB |
#include "werewolf.h"
//author: erray
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/codes/debug.h"
#else
#define debug(...) (void) 37
#endif
struct DSU {
vector<int> link;
DSU(int n) {
link.resize(n);
iota(link.begin(), link.end(), 0);
}
int get(int v) {
return link[v] = (v == link[v] ? v : get(link[v]));
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) {
return false;
}
link[y] = x;
return true;
}
};
struct SegTree {
vector<int> mx;
int n;
SegTree(int _n) : n(_n) {
mx.resize(2 * n + 1, -1);
}
int get(int l, int r) {
int res = -1;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
res = max(res, mx[l++]);
}
if (r & 1) {
res = max(res, mx[--r]);
}
}
return res;
}
void modify(int x, int v) {
for (mx[x += n] = v; x > 1; x >>= 1) {
mx[v >> 1] = max(mx[v], mx[v ^ 1]);
}
}
};
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::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]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
debug(N, g);
auto Convert_to_array = [&](bool rev, vector<int> end, vector<int> ver) {
vector<int> ord(N);
iota(ord.begin(), ord.end(), 0);
if (rev) {
reverse(ord.begin(), ord.end());
}
debug(ord);
DSU d(N);
const int LG = __lg(N) + 1;
vector<vector<int>> lift(LG, vector<int>(N, -1));
vector<vector<int>> ch(N);
for (auto v : ord) {
for (auto u : g[v]) {
if ((u < v) ^ rev && d.get(v) != d.get(u)) {
ch[v].push_back(d.get(u));
lift[0][d.get(u)] = v;
d.unite(v, u);
}
}
}
debug(ch, lift);
for (int l = 1; l < LG; ++l) {
for (int i = 0; i < N; ++i) {
int go = lift[l - 1][i];
lift[l][i] = (go == -1 ? -1 : lift[l - 1][go]);
}
}
vector<int> tin(N), tout(N), tour;
function<void(int)> Dfs = [&](int v) {
tin[v] = int(tour.size());
tour.push_back(v);
for (auto u : ch[v]) {
Dfs(u);
}
tout[v] = int(tour.size()) - 1;
};
Dfs(ord.back());
debug(tin, tout, lift);
vector<int> tour_l(Q), tour_r(Q);
for (int i = 0; i < Q; ++i) {
int v = ver[i];
for (int l = LG - 1; l >= 0; --l) {
if (lift[l][v] != -1 && (!rev? lift[l][v] <= end[i] : lift[l][v] >= end[i])) {
v = lift[l][v];
}
}
tour_l[i] = tin[v];
tour_r[i] = tout[v];
}
return make_tuple(tour, tour_l, tour_r);
};
auto[end_tour, end_l, end_r] = Convert_to_array(false, R, E);
auto[start_tour, start_l, start_r] = Convert_to_array(true, L, S);
debug(end_tour, end_l, end_r);
debug(start_tour, start_l, start_r);
vector<vector<int>> qs(N);
for (int i = 0; i < Q; ++i) {
qs[end_r[i]].push_back(i);
}
vector<int> ind(N);
for (int i = 0; i < N; ++i) {
ind[start_tour[i]] = i;
}
debug(qs, ind);
SegTree st(N);
vector<int> ans(Q);
for (int i = 0; i < N; ++i) {
st.modify(ind[end_tour[i]], i);
for (auto q : qs[i]) {
int mx = st.get(start_l[q], start_r[q]);
ans[q] = (mx >= end_l[q]);
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
732 ms |
64044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
