| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 83507 | radoslav11 | 늑대인간 (IOI18_werewolf) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
We build a prefix and suffix tree with dsu, by incrementing them by 1 vertex at each step. Now queries become:
Do two subtrees have a common vertex (the first subtree is from the prefix tree and the second subtree is from the suffix tree).
This can be done with DFS order + dsu on tree by keeping a set for each vertex. The complexity will be O(N log^2 N + Q log N).
*/
#include <bits/stdc++.h>
#include "werewolf.h"
#include "grader.cpp"
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
using namespace std;
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
int tp[MAXN], sz[MAXN], par[MAXN];
void init(int n)
{
for(int i = 0; i <= n; i++)
par[i] = i, sz[i] = 1, tp[i] = i;
}
int root(int x) { return x == par[x] ? x : (par[x] = root(par[x])); }
bool connected(int u, int v)
{
return root(u) == root(v);
}
void unite(int u, int v)
{
u = root(u), v = root(v);
if(u == v) return;
if(sz[u] > sz[v]) swap(u, v);
par[u] = v;
sz[v] += sz[u];
}
struct Tree
{
vector<int> adj[MAXN];
int st[MAXN], en[MAXN], dfs_time;
void add_edge(int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
void pre_dfs(int u, int pr)
{
st[u] = ++dfs_time;
for(int v: adj[u])
if(v != pr)
pre_dfs(v, u);
en[u] = dfs_time;
}
void order(int root)
{
dfs_time = 0;
pre_dfs(root, root);
}
} t1, t2;
vector<int> adj[MAXN];
vector<int> pref[MAXN], suff[MAXN];
vector<int> ans;
int vert1[MAXN], vert2[MAXN];
set<int> st[MAXN];
vector<int> que[MAXN];
void solve(int u, int pr = -1)
{
st[u].insert(t1.st[u]);
for(int v: t2.adj[u])
if(v != pr)
{
solve(v, u);
if(st[u].size() > st[v].size()) swap(st[u], st[v]);
for(int x: st[v])
st[u].insert(x);
}
for(int i: que[u])
{
int L = t1.st[vert1[i]], R = t1.en[vert1[i]];
auto it = st[u].lower_bound(L);
if(it != st[u].end() && *it <= R)
ans[i] = 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 q = S.size(), m = X.size();
ans.assign(q, 0);
for(int i = 0; i < m; i++)
{
int u = X[i], v = Y[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 0; i < q; i++)
{
suff[L[i]].push_back(i);
pref[R[i]].push_back(i);
}
init(n);
for(int i = 0; i < n; i++)
{
for(int v: adj[i])
if(i > v)
if(!connected(i, v))
{
t1.add_edge(tp[root(i)], tp[root(v)]);
unite(i, v);
tp[root(i)] = i;
}
for(int it: pref[i])
vert1[it] = tp[root(E[it])];
}
int r1 = tp[root(0)];
t1.order(r1);
init(n);
for(int i = n - 1; i >= 0; i--)
{
for(int v: adj[i])
if(i < v)
if(!connected(i, v))
{
t2.add_edge(tp[root(i)], tp[root(v)]);
unite(i, v);
tp[root(i)] = i;
}
for(int it: suff[i])
vert2[it] = tp[root(S[it])];
}
int r2 = tp[root(0)];
t2.order(r2);
for(int i = 0; i < q; i++)
que[vert2[i]].push_back(i);
solve(r2);
return ans;
}