| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 991102 | LaviniaTornaghi | 늑대인간 (IOI18_werewolf) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
template<typename Cmp>
class Tree {
vector<vector<int>> adj;
vector<int> time;
Cmp cmp;
int t;
vector<vector<int>> bin_lift;
vector<pair<int, int>> timer;
vector<int> pos_of;
void dfs(int node, int par = -1) {
if (par != -1) {
bin_lift[node].push_back(par);
for (int i = 0; bin_lift[bin_lift[node][i]].size() > i; i++) {
bin_lift[node].push_back(bin_lift[bin_lift[node][i]][i]);
}
}
timer[node].first = t;
if (adj[node].empty())
pos_of[node] = t++;
for (auto x: adj[node])
dfs(x, node);
timer[node].second = t;
}
public:
pair<int, int> get_range(int node, int limit) {
for (int i = bin_lift[node].size() - 1; i >= 0; i--)
if (bin_lift[node].size() > i && cmp(time[bin_lift[node][i]], limit))
node = bin_lift[node][i];
return timer[node];
}
int get_pos(int node) { return pos_of[node]; }
Tree(int N, const vector<vector<int>> &adj, const vector<int> &time)
: adj(adj), time(time), cmp(), bin_lift(adj.size()), t(0), timer(adj.size()), pos_of(N)
{ dfs(adj.size() - 1); }
};
class DSU {
vector<int> arr;
vector<int> root;
vector<int> time;
vector<vector<int>> adj;
public:
int find(int node) {
if (arr[node] < 0) return node;
return arr[node] = find(arr[node]);
}
void join(int u, int v, int t) {
u = find(u), v = find(v);
if (u == v) return;
if (arr[v] < arr[u]) swap(u, v);
arr[u] += arr[v];
arr[v] = u;
adj.push_back({root[u], root[v]});
time.push_back(t);
root[u] = adj.size() - 1;
}
template<typename Cmp>
Tree<Cmp> get_tree() { return Tree<Cmp>(arr.size(), adj, time); }
DSU(int N, int start_t) : arr(N, -1), root(N), time(N, start_t), adj(N) {
time.reserve(2 * N - 1);
adj.reserve(2 * N - 1);
iota(root.begin(), root.end(), 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
) {
int M = X.size();
int Q = S.size();
vector<vector<int>> adj_wolf(N), adj_human(N);
for (int i = 0; i < M; i++) {
auto [u, v] = minmax(X[i], Y[i]);
adj_human[u].push_back(v);
adj_wolf[v].push_back(u);
}
DSU human_dsu(N, N);
for (int i = N - 1; i >= 0; i--)
for (auto j: adj_human[i])
human_dsu.join(i, j, i);
Tree human_tree = human_dsu.get_tree<greater_equal<int>>();
DSU wolf_dsu(N, -1);
for (int i = 0; i < N; i++)
for (auto j: adj_wolf[i])
wolf_dsu.join(i, j, i);
Tree wolf_tree = wolf_dsu.get_tree<less_equal<int>>();
vector<vector<bool>> grid(N, vector<bool>(N));
for (int i = 0; i < N; i++)
grid[human_tree.get_pos(i)][wolf_tree.get_pos(i)] = true;
vector<int> ans(Q);
for (int i = 0; i < Q; i++) {
auto [l1, r1] = human_tree.get_range(S[i], L[i]);
auto [l2, r2] = wolf_tree.get_range(E[i], R[i]);
for (int x = l1; x < r1; x++)
for (int y = l2; y < r2; y++)
ans[i] |= grid[x][y];
}
return ans;
}