| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1295979 | baodat | Werewolf (IOI18_werewolf) | C++20 | 0 ms | 0 KiB |
// problem1.cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, l, r) for(int i = l; i <= r; i++)
#define FORD(i, l, r) for(int i = l; i >= r; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sp(x) setprecision(x) << fixed
#define db double
#define ldb long double
#define ff first
#define ss second
#define pb push_back
#define ins insert
typedef vector<int> vi;
struct DSU{
int n;
vector<int> par, sz;
DSU(int __n = 0){
init(__n);
}
void init(int __n){
n = __n;
par.assign(n + 1, 0);
sz.assign(n + 1, 1);
iota(all(par), 0);
}
int find_u(int u){
return u == par[u] ? u : par[u] = find_u(par[u]);
}
bool unite(int u, int v){
u = find_u(u);
v = find_u(v);
if(u == v) return false;
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
par[v] = u;
return true;
}
};
struct BIT{
int n;
vector<int> bit;
BIT(int __n = 0){
init(__n);
}
void init(int __n){
n = __n;
bit.assign(n + 1, 0);
}
void update(int i, int v){
while(i <= n){
bit[i] += v;
i += i &-i;
}
}
int query(int i){
int s = 0;
while(i > 0){
s += bit[i];
i -= i &-i;
}
return s;
}
int query(int l, int r){
return query(r) - query(l - 1);
}
};
const int N = 2e5 + 5;
const int LOG = 20;
int lca_human[2 * N][LOG], lca_wolf[2 * N][LOG];
int tin_human[2 * N], tout_human[2 * N], tin_wolf[2 * N], tout_wolf[2 * N];
int n, m, q, krt_human_w[2 * N], krt_wolf_w[2 * N], pos_human[2 * N], pos_wolf[2 * N];
vi x, y, s, e, l, r;
vi krt_human[2 * N], krt_wolf[2 * N], adj[N];
int timer = 0;
int lift_human(int u, int L){
if(krt_human_w[u] < L) return -1;
FORD(j, LOG - 1, 0){
int p = lca_human[u][j];
if(p != -1 && krt_human_w[p] >= L) u = p;
}
return u;
}
int lift_wolf(int u, int R){
if(krt_wolf_w[u] > R) return -1;
FORD(j, LOG - 1, 0){
int p = lca_wolf[u][j];
if(p != -1 && krt_wolf_w[p] <= R) u = p;
}
return u;
}
void dfs_human(int u, int p){
tin_human[u] = 1e9;
tout_human[u] = 0;
if(u < n){
pos_human[u] = ++timer;
tin_human[u] = tout_human[u] = pos_human[u];
}
for(int v : krt_human[u]){
if(v == p) continue;
if(v > u) continue;
lca_human[v][0] = u;
FOR(j, 1, LOG - 1){
if(lca_human[v][j - 1] != -1)
lca_human[v][j] = lca_human[lca_human[v][j - 1]][j - 1];
}
dfs_human(v, u);
tin_human[u] = min(tin_human[u], tin_human[v]);
tout_human[u] = max(tout_human[u], tout_human[v]);
}
}
void dfs_wolf(int u, int p){
tin_wolf[u] = 1e9;
tout_wolf[u] = 0;
if(u < n){
pos_wolf[u] = ++timer;
tin_wolf[u] = tout_wolf[u] = pos_wolf[u];
}
for(int v : krt_wolf[u]){
if(v == p) continue;
if(v > u) continue;
lca_wolf[v][0] = u;
FOR(j, 1, LOG - 1){
if(lca_wolf[v][j - 1] != -1)
lca_wolf[v][j] = lca_wolf[lca_wolf[v][j - 1]][j - 1];
}
dfs_wolf(v, u);
tin_wolf[u] = min(tin_wolf[u], tin_wolf[v]);
tout_wolf[u] = max(tout_wolf[u], tout_wolf[v]);
}
}
void build_human_tree(){
int sz = 2 * n;
DSU dsu(sz);
vi val(n);
int id = n + 1;
vector<bool> visited(n, false);
FOR(i, 0, 2 * n - 1) krt_human_w[i] = i;
iota(all(val), 0);
reverse(all(val));
FORD(i, n - 1, 0){
visited[i] = true;
for(int v : adj[i]){
if(!visited[v]) continue;
int r_i = dsu.find_u(i);
int r_v = dsu.find_u(v);
if(r_i == r_v) continue;
int x = id++;
int node_u = val[r_i], node_v = val[r_v];
krt_human[x].pb(node_u);
krt_human[node_u].pb(x);
krt_human[x].pb(node_v);
krt_human[node_v].pb(x);
krt_human_w[x] = i;
dsu.unite(r_i, r_v);
val[dsu.find_u(r_i)] = x;
}
}
timer = 0;
FORD(i, 2 * n - 1, 0){
if(lca_human[i][0] == -1){
dfs_human(i, -1);
}
}
}
void build_wolf_tree(){
int sz = 2 * n;
DSU dsu(n);
vi val(n);
int id = n + 1;
vector<bool> visited(n, false);
iota(all(val), 0);
FOR(i, 0, 2 * n - 1) krt_wolf_w[i] = i;
FOR(i, 0, n - 1){
visited[i] = true;
for(int v : adj[i]){
if(!visited[v]) continue;
int r_i = dsu.find_u(i);
int r_v = dsu.find_u(v);
if(r_i == r_v) continue;
int x = id++;
int node_u = val[r_i], node_v = val[r_v];
krt_wolf[x].pb(node_u);
krt_wolf[node_u].pb(x);
krt_wolf[x].pb(node_v);
krt_wolf[node_v].pb(x);
krt_wolf_w[x] = i;
dsu.unite(r_i, r_v);
val[dsu.find_u(r_i)] = x;
}
}
timer = 0;
FORD(i, 2 * n - 1, 0){
if(lca_wolf[i][0] == -1){
dfs_wolf(i, -1);
}
}
}
struct event{
int x, yl, yr, id, type;
};
vi check_validity(int __n, vi __x, vi __y, vi __s, vi __e, vi __l, vi __r){
n = __n;
x = __x;
y = __y;
s = __s;
e = __e;
l = __l;
r = __r;
FOR(i, 0, n - 1) adj[i].clear();
FOR(i, 0, 2 * n - 1){
krt_human[i].clear();
krt_wolf[i].clear();
}
timer = 0;
memset(lca_wolf, -1, sizeof lca_wolf);
memset(lca_human, -1, sizeof lca_human);
m = x.size();
q = s.size();
assert(q == e.size());
assert(m == y.size());
FOR(i, 0, m - 1){
adj[x[i]].pb(y[i]);
adj[y[i]].pb(x[i]);
}
build_wolf_tree();
build_human_tree();
//cerr << "can't build";
vector<pair<int, int>> points(n);
FOR(i, 0, n - 1){
points[i] = {pos_human[i], pos_wolf[i]}; //x y
//x -> human
}
//cerr << "hi";
sort(all(points));
vector<event> ev;
vector<int>ans(q, 0);
FOR(i, 0, q - 1){
int par_human = lift_human(s[i], l[i]);
int par_wolf = lift_wolf(e[i], r[i]);
if(par_human == -1 || par_wolf == -1) continue;
//ox la then human, oy la theo wolf
ev.pb({tout_human[par_human], tin_wolf[par_wolf], tout_wolf[par_wolf], i, 1});
ev.pb({tin_human[par_human] - 1, tin_wolf[par_wolf], tout_wolf[par_wolf], i, -1});
}
sort(all(ev), [&](event a, event b){
return a.x < b.x;
});
// cerr << "Step1";
BIT bit(n + 1);
int it = 0;
for(event e : ev){
while(it < n && points[it].first <= e.x){
bit.update(points[it].second, 1);
++it;
}
ans[e.id] += (bit.query(e.yl, e.yr) * e.type);
}
FOR(i, 0, q - 1) ans[i] = (ans[i] > 0 ? 1 : 0);
return ans;
}
void solve(){
int n = 6, m = 6, q = 3;
vi x = {5, 1, 1, 3, 3, 5};
vi y = {1, 2, 3, 4, 0, 2};
vi s = {4, 4, 5};
vi e = {2, 2, 4};
vi l = {1, 2, 3};
vi r = {2, 2, 4};
vi ans = check_validity(n, x, y, s, e, l, r);
for(int i : ans) cout << i << " ";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}