#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define isz(a) ((signed)a.size())
constexpr int N = 2e5 + 5, M = 4e5 + 5, Q = 2e5 + 5;
constexpr int NODE = 4e5 + 5;
constexpr int inf = 1e9 + 7;
struct merge_sort_tree{
vector <int> seg[1 << 19];
void build(int id, int l, int r, int a[]){
if (l == r){
seg[id].emplace_back(a[l]);
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid, a);
build(id * 2 + 1, mid + 1, r, a);
merge(seg[id * 2].begin(), seg[id * 2].end(), seg[id * 2 + 1].begin(), seg[id * 2 + 1].end(), back_inserter(seg[id]));
}
int query(int id, int l, int r, int u, int v, int val){
if (v < l or r < u){
return inf;
}
if (u <= l and r <= v){
auto itr = lower_bound(seg[id].begin(), seg[id].end(), val);
return itr == seg[id].end() ? inf : *itr;
}
int mid = (l + r) >> 1;
return min(query(id * 2, l, mid, u, v, val), query(id * 2 + 1, mid + 1, r, u, v, val));
}
} seg;
struct Disjoint_set{
int par[N];
void reset(int sz = N){
fill(par, par + sz, -1);
}
Disjoint_set(){
reset();
}
int root(int x){
return par[x] < 0 ? x : (par[x] = root(par[x]));
}
bool share(int x, int y){
return root(x) == root(y);
}
bool merge(int x, int y){
if ((x = root(x)) == (y = root(y))){
return false;
}
if (par[x] > par[y]){
swap(x, y);
}
par[x] += par[y];
par[y] = x;
return true;
}
};
struct Query{
int s, t, l, r;
};
int n, m, q;
vector <int> adj[N];
Query query[Q];
vector <int> adj_werewolf[NODE], adj_human[NODE];
int root_werewolf, root_human;
int node_werewolf[Q], node_human[Q];
int ctrtour, tour[NODE], tin[NODE], tout[NODE];
void dfs_tour(vector <int> adj[], int u){
tour[ctrtour] = u;
tin[u] = ctrtour;
ctrtour++;
for (auto v: adj[u]){
dfs_tour(adj, v);
}
tout[u] = ctrtour;
}
pair <int, int> tour_range_werewolf[Q], tour_range_human[Q];
int pos_human[N], pos_werewolf[N];
int pos[2 * N];
int ans[Q];
vector <int> check_validity(int _n, vector <int> _u, vector <int> _v, vector <int> _s, vector <int> _e, vector <int> _l, vector <int> _r){
n = _n;
m = isz(_u);
for (int i = 0; i < m; i++){
int u = _u[i], v = _v[i];
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
q = isz(_s);
for (int i = 0; i < q; i++){
int s = _s[i], t = _e[i], l = _l[i], r = _r[i];
query[i] = Query{s, t, l, r};
}
{ // Human
vector <pair <int, int>> query_human;
for (int i = 0; i < q; i++){
query_human.emplace_back(query[i].l, i);
}
sort(query_human.begin(), query_human.end());
Disjoint_set dsu;
vector <int> current_node(n);
iota(current_node.begin(), current_node.end(), 0);
root_human = n;
for (int u = n - 1; u >= 0; u--){
for (auto v: adj[u]){
if (v < u){
continue;
}
if (not dsu.share(u, v)){
int x = current_node[dsu.root(u)], y = current_node[dsu.root(v)];
dsu.merge(u, v);
adj_human[root_human].emplace_back(x);
adj_human[root_human].emplace_back(y);
current_node[dsu.root(u)] = root_human;
root_human++;
}
}
while (not query_human.empty() and query_human.back().first == u){
int i = query_human.back().second;
node_human[i] = current_node[dsu.root(query[i].s)];
query_human.pop_back();
}
}
dfs_tour(adj_human, root_human - 1);
for (int i = 0; i < q; i++){
tour_range_human[i] = pair{tin[node_human[i]], tout[node_human[i]]};
}
for (int u = 0; u < n; u++){
pos_human[u] = tin[u];
}
}
{ // Werewolf
vector <pair <int, int>> query_werewolf;
for (int i = 0; i < q; i++){
query_werewolf.emplace_back(query[i].r, i);
}
sort(query_werewolf.begin(), query_werewolf.end(), greater <>());
Disjoint_set dsu;
vector <int> current_node(n);
iota(current_node.begin(), current_node.end(), 0);
root_werewolf = n;
for (int u = 0; u < n; u++){
for (auto v: adj[u]){
if (v > u){
continue;
}
if (dsu.merge(u, v)){
int x = current_node[dsu.root(u)], y = current_node[dsu.root(v)];
dsu.merge(u, v);
adj_werewolf[root_werewolf].emplace_back(x);
adj_werewolf[root_werewolf].emplace_back(y);
current_node[dsu.root(u)] = root_werewolf;
root_werewolf++;
}
}
while (not query_werewolf.empty() and query_werewolf.back().first == u){
int i = query_werewolf.back().second;
node_werewolf[i] = current_node[dsu.root(query[i].t)];
query_werewolf.pop_back();
}
}
dfs_tour(adj_werewolf, root_werewolf - 1);
for (int i = 0; i < q; i++){
tour_range_werewolf[i] = pair{tin[node_werewolf[i]], tout[node_werewolf[i]]};
}
for (int u = 0; u < n; u++){
pos_werewolf[u] = tin[u];
}
}
fill(pos, pos + root_human, inf);
for (int u = 0; u < n; u++){
pos[pos_human[u]] = pos_werewolf[u];
}
seg.build(1, 0, root_human - 1, pos);
for (int i = 0; i < q; i++){
if (seg.query(1, 0, root_human - 1, tour_range_human[i].first, tour_range_human[i].second, tour_range_werewolf[i].first) <= tour_range_werewolf[i].second){
ans[i] = 1;
}
else{
ans[i] = 0;
}
}
return vector <int>(ans, ans + q);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
61 ms |
80972 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
61 ms |
80972 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
362 ms |
168724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
61 ms |
80972 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
