| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 394852 | blue | Werewolf (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "werewolf.h"
#include <vector>
#include <algorithm>
using namespace std;
/*
Algorithm:
(1) Build a tree:
Sort nodes in descending order.
For a node X, go through all of its edges to higher nodes Y.
Create an edge from root(X) to Y, and set root(Z) to Y for all descendents Z of previous root(X).
For every node, for any value of L, the set of nodes visitable as a human form a subtree.
Use merge sort tree for queries.
*/
const int maxN = 200000;
vector<int> edge[maxN];
vector<int> col(maxN);
vector<int> col_list[maxN];
vector<int> minV(maxN); //min value in color i.
vector<int> child1[maxN];
vector<int> order1;
vector<int> pos1(maxN);
vector<int> subtree1(maxN, 1);
int anc1[maxN][20];
vector<int> depth1(maxN);
void dfs1(int u)
{
// cerr << "dfs1 " << u << '\n';
pos1[u] = int(order1.size());
order1.push_back(u);
for(int v: child1[u])
{
anc1[v][0] = u;
for(int e = 1; e < 20; e++)
anc1[v][e] = anc1[ anc1[v][e-1] ][e-1];
depth1[v] = depth1[u] + 1;
dfs1(v);
subtree1[u] += subtree1[v];
}
}
vector<int> maxV(maxN);
vector<int> child2[maxN];
vector<int> order2;
vector<int> pos2(maxN);
vector<int> subtree2(maxN, 1);
int anc2[maxN][20];
vector<int> depth2(maxN);
void dfs2(int u)
{
pos2[u] = int(order2.size());
order2.push_back(u);
for(int v: child2[u])
{
anc2[v][0] = u;
for(int e = 1; e < 20; e++)
anc2[v][e] = anc2[ anc2[v][e-1] ][e-1];
depth2[v] = depth2[u] + 1;
dfs2(v);
subtree2[u] += subtree2[v];
}
}
vector<int> init(maxN);
struct segtree
{
int l;
int r;
vector<int> V;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r)
{
V.push_back(init[l]);
}
else
{
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
for(int v: left->V) V.push_back(v);
for(int v: right->V) V.push_back(v);
sort(V.begin(), V.end());
}
}
// segtree range, value range
bool query(int L, int R, int X, int Y)
{
if(R < l || r < L) return 0;
else if(L <= l && r <= R)
{
int s = -1;
for(int e = 19; e >= 0; e--)
{
if(s + (1 << e) >= V.size()) continue;
if(V[s + (1 << e)] <= Y)
s += (1 << e);
}
if(s == -1) return 0;
return (V[s] >= X);
}
else return left->query(L, R, X, Y) || right->query(L, R, X, Y);
}
};
segtree T;
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 = X.size();
for(int j = 0; j < M; j++)
{
edge[X[j]].push_back(Y[j]);
edge[Y[j]].push_back(X[j]);
}
for(int e = 0; e < 20; e++)
{
anc1[0][e] = 0;
anc2[N-1][e] = N-1;
}
depth1[0] = 0;
depth2[N-1] = 0;
//Compute human values
for(int i = 0; i < N; i++)
{
col_list[i].push_back(i);
col[i] = minV[i] = i;
}
for(int u = N-1; u >= 0; u--)
{
for(int v: edge[u])
{
if(v < u) continue;
if(col[v] == col[u]) continue;
child1[u].push_back(minV[col[v]]);
int U = u, V = v;
if(col_list[col[U]].size() < col_list[col[V]].size())
swap(U, V);
int colV = col[V];
for(int x: col_list[colV])
{
col[x] = col[U];
col_list[col[U]].push_back(x);
}
minV[col[U]] = u;
}
}
dfs1(0);
for(int i = 0; i < N; i++) cerr << order1[i] << ' ';
cerr << '\n';
//Compute werewolf values
for(int i = 0; i < N; i++)
{
col_list[i].clear();
col_list[i].push_back(i);
col[i] = maxV[i] = i;
}
for(int u = 0; u < N; u++)
{
for(int v: edge[u])
{
if(v > u) continue;
if(col[v] == col[u]) continue;
child2[u].push_back(maxV[col[v]]);
int U = u, V = v;
if(col_list[col[U]].size() < col_list[col[V]].size())
swap(U, V);
int colV = col[V];
for(int x: col_list[colV])
{
col[x] = col[U];
col_list[col[U]].push_back(x);
}
maxV[col[U]] = u;
}
}
dfs2(N-1);
for(int i = 0; i < N; i++) init[ pos1[i] ] = pos2[i];
T = segtree(0, N-1);
int Q = S.size();
vector<int> res(Q);
for(int i = 0; i < N; i++)
{
cerr << i << ": ";
for(int e = 0; e < 5; e++) cerr << anc2[i][e] << ' ';
cerr << '\n';
}
cerr << "----------\n";
for(int i = 0; i < Q; i++)
{
int s = S[i], e = E[i], l = L[i], r = R[i];
cerr << s << ' ' << e << ' ' << l << ' ' << r << '\n';
// if(depth1[s] > depth1[l]) swap(s, l);
// // cerr << "s = " << s << " ,l = " << l << '\n';
// for(int x = 19; x >= 0; x--)
// {
// if(depth1[l] - (1 << x) < depth1[s]) continue;
// l = anc1[l][x];
// }
//
// for(int x = 19; x >= 0; x--)
// {
// if(anc1[s][x] == anc1[l][x]) continue;
// s = anc1[s][x];
// l = anc1[l][x];
// }
// if(s != l)
// s = l = anc1[s][0];
for(int x = 19; x >= 0; x--)
{
if(anc1[s][x] >= l)
s = anc1[s][x];
}
// if(depth2[e] > depth2[r]) swap(e, r);
// for(int x = 19; x >= 0; x--)
// {
// if(depth2[r] - (1 << x) < depth2[e]) continue;
// r = anc2[r][x];
// }
//
// for(int x = 19; x >= 0; x--)
// {
// if(anc2[e][x] == anc2[r][x]) continue;
// e = anc2[e][x];
// r = anc2[r][x];
// }
// if(e != r)
// e = r = anc2[e][0];
for(int x = 19; x >= 0; x--)
{
if(anc2[e][x] <= r)
e = anc2[e][x];
}
cerr << "i: " << s << ' ' << e << '\n';
cerr << "query: " << pos1[s] << ' ' << pos1[s] + subtree1[s] - 1 << ' ';
cerr << pos2[e] << ' ' << pos2[e] + subtree2[e] - 1 << '\n';
res[i] = T.query(pos1[s], pos1[s] + subtree1[s] - 1, pos2[e], pos2[e] + subtree2[e] - 1);
}
for(int i = 0; i < N; i++) cerr << order1[i] << ' ';
cerr << '\n';
for(int i = 0; i < N; i++) cerr << order2[i] << ' ';
cerr << '\n';
return res;
}