| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 332548 |
2020-12-02T20:30:20 Z |
pit4h |
Werewolf (IOI18_werewolf) |
C++14 |
|
2005 ms |
524292 KB |
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+2, MAXM = 4e5+2, Log = 20;
vector<int> ans;
int Find(int x, vector<int>& f) {
if(f[x] == x) return x;
f[x] = Find(f[x], f);
return f[x];
}
bool Union(int x, int y, vector<int>& f, vector<int>& cnt, vector<int>& mx, bool dir) {
x = Find(x, f); y = Find(y, f);
if(x==y) return false;
if(cnt[x] < cnt[y]) swap(x, y);
cnt[x] += cnt[y];
cnt[y] = 0;
f[y] = x;
if(!dir) {
mx[x] = max(mx[x], mx[y]);
}
else {
mx[x] = min(mx[x], mx[y]);
}
return true;
}
struct Query {
int l, r, id;
};
struct Node {
int l, r, val;
Node *ls = NULL, *rs = NULL;
Node(int _l, int _r) {
l = _l; r = _r; val=0;
}
void push() {
if(!ls) {
ls = new Node(l, (l+r)/2);
rs = new Node((l+r)/2+1, r);
}
}
};
struct Segtree {
vector<int> updates;
Node *root;
Segtree(int _N) {
root = new Node(0, _N-1);
}
void ins(int x, Node* cur) {
if(x > (cur->r) || x < (cur->l)) {
return;
}
cur->val++;
if((cur->l) == (cur->r)) return;
cur->push();
ins(x, cur->ls);
ins(x, cur->rs);
}
void upd(int x) {
updates.push_back(x);
ins(x, root);
}
int qry(int l, int r, Node* cur) {
if(l > (cur->r) || r < (cur->l)) {
return 0;
}
if(l <= (cur->l) && r >= (cur->r)) {
return cur->val;
}
cur->push();
return qry(l, r, cur->ls) + qry(l, r, cur->rs);
}
void clr() {
updates.clear();
}
};
Segtree *occ[MAXN];
struct Form {
vector<vector<int>> g, anc;
vector<vector<Query>> queries;
vector<int> pre, range;
int N, nr=0;
Form *other;
Form(int _N) {
N = _N;
g.resize(N); anc.resize(Log, vector<int>(N));
pre.resize(N); range.resize(N);
queries.resize(N);
}
void build_graph(vector<int>& X, vector<int>& Y, vector<int>& order) {
int M = X.size();
vector<int> f(N), cnt(N), mx(N); for(int i=0; i<N; ++i) f[i] = mx[i] = i, cnt[i]=1;
vector<vector<int>> G(N);
for(int i=0; i<M; ++i) {
if( (X[i] < Y[i]) != (order[0] < order.back()) ) {
swap(X[i], Y[i]);
}
G[Y[i]].push_back(X[i]);
}
for(int i: order) {
for(int j: G[i]) {
int repj = mx[Find(j, f)];
if(Union(i, j, f, cnt, mx, (order[0] > order.back()) )) {
g[i].push_back(repj);
}
}
}
}
void build_anc() {
for(int j=1; j<Log; ++j) {
for(int i=0; i<N; ++i) {
anc[j][i] = anc[j-1][anc[j-1][i]];
}
}
}
void dfs(int x, int par) {
anc[0][x] = par;
pre[x] = nr; nr++;
range[x] = pre[x];
for(int i: g[x]) {
dfs(i, x);
range[x] = max(range[x], range[i]);
}
if(x==par) {
build_anc();
}
}
int lowest_ancestor(int x, int h) {
for(int i=Log-1; i>=0; --i) {
if(x==h) break;
if(anc[i][x]==h || (x < h) == (anc[i][x] < h)) {
x = anc[i][x];
}
}
return x;
}
void solve(int x, int p) {
int big_child = -1;
for(int i: g[x]) {
solve(i, x);
if(big_child==-1 || occ[i]->updates.size() > occ[big_child]->updates.size()) {
big_child = i;
}
}
if(big_child==-1) {
occ[x] = new Segtree(N);
}
else {
occ[x] = occ[big_child];
}
for(int i: g[x]) {
if(i!=big_child) {
for(int j: occ[i]->updates) {
occ[x]->upd(j);
}
occ[i]->clr();
}
}
occ[x]->upd(other->pre[x]);
for(auto q: queries[x]) {
ans[q.id] = (occ[x]->qry(q.l, q.r, occ[x]->root) > 0);
}
}
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
swap(S, E); // == swap(human, wolf)
int Q = S.size();
ans.resize(Q);
vector<int> order;
for(int i=0; i<N; ++i) order.push_back(i);
Form human(N), wolf(N);
wolf.other = &human;
human.build_graph(X, Y, order);
reverse(order.begin(), order.end());
wolf.build_graph(X, Y, order);
human.dfs(N-1, N-1);
wolf.dfs(0, 0);
for(int i=0; i<Q; ++i) {
S[i] = human.lowest_ancestor(S[i], R[i]);
E[i] = wolf.lowest_ancestor(E[i], L[i]);
if(S[i] > R[i] || E[i] < L[i]) continue;
wolf.queries[E[i]].push_back({human.pre[S[i]], human.range[S[i]], i});
}
wolf.solve(0, 0);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
492 KB |
Output is correct |
| 10 |
Correct |
14 ms |
5484 KB |
Output is correct |
| 11 |
Correct |
13 ms |
5868 KB |
Output is correct |
| 12 |
Correct |
15 ms |
6892 KB |
Output is correct |
| 13 |
Correct |
14 ms |
7148 KB |
Output is correct |
| 14 |
Correct |
17 ms |
9068 KB |
Output is correct |
| 15 |
Correct |
11 ms |
3692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2005 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
492 KB |
Output is correct |
| 10 |
Correct |
14 ms |
5484 KB |
Output is correct |
| 11 |
Correct |
13 ms |
5868 KB |
Output is correct |
| 12 |
Correct |
15 ms |
6892 KB |
Output is correct |
| 13 |
Correct |
14 ms |
7148 KB |
Output is correct |
| 14 |
Correct |
17 ms |
9068 KB |
Output is correct |
| 15 |
Correct |
11 ms |
3692 KB |
Output is correct |
| 16 |
Runtime error |
2005 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 17 |
Halted |
0 ms |
0 KB |
- |
