| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1197057 | _callmelucian | Werewolf (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
struct DSU {
vector<int> lab;
DSU (int sz) : lab(sz + 1, -1) {}
int get (int u) {
if (lab[u] < 0) return u;
return lab[u] = get(lab[u]);
}
int getSz (int u) { return -lab[get(u)]; }
bool unite (int a, int b) {
a = get(a), b = get(b);
if (a == b) return 0;
if (-lab[a] < -lab[b]) swap(a, b);
lab[a] += lab[b], lab[b] = a;
return 1;
}
};
struct queryItem {
int st, en, bound, idx;
queryItem() : st(0), en(0), bound(0), idx(0) {}
queryItem (int st, int en, int bound, int idx) :
st(st), en(en), bound(bound), idx(idx) {}
};
const int mn = 6e5 + 5;
int sz[mn], num[mn], chain[mn], depth[mn], par[mn], weight[mn], top[mn], timeDfs;
vector<int> graphAdj[mn], adj[mn];
vector<queryItem> queries[mn];
// custom comparator for set
struct setComp {
bool operator() (int a, int b) { return num[a] < num[b]; }
};
set<int, setComp> markedNode[mn];
void addEdge (int par, int u) {
adj[par].push_back(top[u]);
top[u] = par;
}
int szDfs (int u) {
sz[u] = 1;
for (int v : adj[u]) sz[u] += szDfs(v);
return sz[u];
}
void dfs (int u, int p, int d, bool toP) {
num[u] = ++timeDfs, par[u] = p, depth[u] = d;
chain[u] = (toP ? chain[p] : u);
sort(all(adj[u]), [&] (int a, int b) { return sz[a] > sz[b]; });
bool heavy = 1;
for (int v : adj[u])
dfs(v, u, d + 1, heavy), heavy = 0;
}
int lca (int a, int b) {
int ap = par[chain[a]], bp = par[chain[b]];
while (chain[a] != chain[b]) {
if (depth[ap] == depth[bp]) {
a = ap, ap = par[chain[a]];
b = bp, bp = par[chain[b]];
}
else if (depth[ap] > depth[bp]) a = ap, ap = par[chain[a]];
else if (depth[bp] > depth[ap]) b = bp, bp = par[chain[b]];
}
return (depth[a] < depth[b] ? a : b);
}
vector<int> check_validity (int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
/// process input and prepare offline queries
// int M = sizeof(X) / sizeof(X[0]), Q = sizeof(S) / sizeof(S[0]);
int M = X.size(), Q = S.size();
for (int i = 0; i < M; i++) {
graphAdj[X[i]].push_back(Y[i]);
graphAdj[Y[i]].push_back(X[i]);
}
for (int i = 0; i < Q; i++)
queries[L[i]].emplace_back(S[i], E[i], R[i], i);
/// build DSU tree for MST (with Kruskal)
int node = N - 1; DSU dsu(N);
for (int i = 0; i < N; i++) {
bool firstMerge = 1;
for (int j : graphAdj[i]) {
if (j > i || !dsu.unite(i, j)) continue;
if (firstMerge)
firstMerge = 0, addEdge(++node, i);
addEdge(node, j);
}
if (!firstMerge) weight[node] = i;
weight[i] = i;
}
/// process DSU tree
szDfs(node), dfs(node, 0, 1, 0);
/// build MST (max) and process queries
vector<int> res(Q);
dsu = DSU(N);
for (int i = 0; i < N; i++) markedNode[i].insert(i);
for (int i = N - 1; i >= 0; i--) {
for (int j : graphAdj[i]) {
int u = dsu.get(i), v = dsu.get(j);
if (j > i && dsu.unite(i, j)) {
if (u == dsu.get(i)) swap(u, v);
for (int iter : markedNode[u])
markedNode[v].insert(iter);
markedNode[u].clear();
}
}
for (queryItem &iter : queries[i]) {
int root = dsu.get(iter.st), opt = INT_MAX;
auto it = markedNode[root].lower_bound(iter.en);
if (it != markedNode[root].end()) {
int lc = lca(iter.en, *it);
opt = min(opt, weight[lc]);
}
if (it != markedNode[root].begin()) {
int lc = lca(iter.en, *prev(it));
opt = min(opt, weight[lc]);
}
res[iter.idx] = (opt <= iter.bound);
// cout << "query " << iter.idx << " " << opt << " " << iter.bound << endl;
// for (int u : markedNode[root]) cout << u << " ";
// cout << endl;
}
}
return res;
}
#ifdef LOCAL
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
vector<int> X = {5, 1, 1, 3, 3, 5};
vector<int> Y = {1, 2, 3, 4, 0, 2};
vector<int> S = {4, 4, 5};
vector<int> E = {2, 2, 4};
vector<int> L = {1, 2, 3};
vector<int> R = {2, 2, 4};
// cout << sizeof(X) << " ";
vector<int> res = check_validity(6, X, Y, S, E, L, R);
for (int u : res) cout << u << " ";
return 0;
}
#endif LOCAL