#include "werewolf.h"
#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;
#define NN 200000
int hi[NN], lo[NN];
template< const int& (*c)(const int&, const int&) >
struct kruskal_reconstruction_tree
{
vector<int> p, tin, tout;
vector<vector<int>> g;
int l;
kruskal_reconstruction_tree(int n, int n0) : p(n), l(n0), g(n), tin(n), tout(n)
{
iota(p.begin(), p.end(), 0);
}
int find(int x)
{
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
int unite(int x, int y)
{
x = find(x); y = find(y);
if (x == y) return 0;
g[p[x] = p[y] = ++l] = {x, y};
return 1;
}
int timer = 0;
void dfs(int u, int p)
{
tin[u] = timer++;
for (auto v : g[u]) if (v != p) dfs(v, u);
tout[u] = timer - 1;
}
void compute()
{
for (int i = l; i--;) if (!tin[i]) dfs(i, i);
}
};
kruskal_reconstruction_tree<max> krt1(NN<<2, NN);
kruskal_reconstruction_tree<min> krt2(NN<<2, NN);
vector<int> t[NN<<2];
void add(int v, int l, int r, int p, int k)
{
t[v].push_back(k);
if (l == r) return;
if (p <= (l+r)/2) add(2*v+1, l, (l+r)/2, p, k);
else add(2*v+1, (l+r)/2+1, r, p, k);
}
int qry(int v, int l, int r, int x, int y, int k)
{
if (r < x || y < l) return 1e9;
if (x <= l && r <= y)
{
auto it = lower_bound(t[v].begin(), t[v].end(), k);
return it == t[v].end() ? 1e9 : *it;
}
return min(qry(2*v+1, l, (l+r)/2, x, y, k), qry(2*v+2, (l+r)/2+1, r, x, y, k));
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
for (int i = 0; i <= N; ++i) lo[i] = 1e9;
int Q = S.size();
vector<int> A(Q);
vector<vector<int>> g(N);
for (int i = 0; i < (int)X.size(); ++i) g[X[i]].push_back(Y[i]), g[Y[i]].push_back(X[i]);
/* build krt */
vector<int> rtl(Q), rtr(Q);
{
vector<vector<int>> byl(N), byr(N);
for (int i = 0; i < Q; ++i) byl[L[i]].push_back(i), byr[R[i]].push_back(i);
for (int i = N; i--;)
{
for (auto v : g[i]) krt1.unite(v, i);
for (auto j : byl[L[i]]) rtl[j] = krt1.l;
}
for (int i = 0; i < N; ++i)
{
for (auto v : g[i]) krt2.unite(v, i);
for (auto j : byr[R[i]]) rtr[j] = krt2.l;
}
}
/* euler tour and stuff */
krt1.compute();
krt2.compute();
/* build merge sort tree */
vector<pair<int, int>> ins;
for (int i = 0; i < (int)X.size(); ++i)
{
if (X[i] > Y[i]) swap(X[i], Y[i]);
ins.emplace_back(krt2.tin[X[i]], krt1.tin[Y[i]]);
}
sort(ins.begin(), ins.end());
for (auto [b, a] : ins) add(0, 0, N, a, b);
for (int i = 0; i < Q; ++i)
{
auto u = qry(0, 0, N, krt1.tin[rtl[i]], krt1.tout[rtl[i]], krt2.tin[rtr[i]]);
A[i] = u <= krt2.tin[rtr[i]];
}
return A;
}
Compilation message
werewolf.cpp: In instantiation of 'kruskal_reconstruction_tree<c>::kruskal_reconstruction_tree(int, int) [with const int& (* c)(const int&, const int&) = std::max<int>]':
werewolf.cpp:51:48: required from here
werewolf.cpp:15:9: warning: 'kruskal_reconstruction_tree<std::max<int> >::l' will be initialized after [-Wreorder]
15 | int l;
| ^
werewolf.cpp:14:25: warning: 'std::vector<std::vector<int> > kruskal_reconstruction_tree<std::max<int> >::g' [-Wreorder]
14 | vector<vector<int>> g;
| ^
werewolf.cpp:17:5: warning: when initialized here [-Wreorder]
17 | kruskal_reconstruction_tree(int n, int n0) : p(n), l(n0), g(n), tin(n), tout(n)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:14:25: warning: 'kruskal_reconstruction_tree<std::max<int> >::g' will be initialized after [-Wreorder]
14 | vector<vector<int>> g;
| ^
werewolf.cpp:13:20: warning: 'std::vector<int> kruskal_reconstruction_tree<std::max<int> >::tin' [-Wreorder]
13 | vector<int> p, tin, tout;
| ^~~
werewolf.cpp:17:5: warning: when initialized here [-Wreorder]
17 | kruskal_reconstruction_tree(int n, int n0) : p(n), l(n0), g(n), tin(n), tout(n)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp: In instantiation of 'kruskal_reconstruction_tree<c>::kruskal_reconstruction_tree(int, int) [with const int& (* c)(const int&, const int&) = std::min<int>]':
werewolf.cpp:52:48: required from here
werewolf.cpp:15:9: warning: 'kruskal_reconstruction_tree<std::min<int> >::l' will be initialized after [-Wreorder]
15 | int l;
| ^
werewolf.cpp:14:25: warning: 'std::vector<std::vector<int> > kruskal_reconstruction_tree<std::min<int> >::g' [-Wreorder]
14 | vector<vector<int>> g;
| ^
werewolf.cpp:17:5: warning: when initialized here [-Wreorder]
17 | kruskal_reconstruction_tree(int n, int n0) : p(n), l(n0), g(n), tin(n), tout(n)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:14:25: warning: 'kruskal_reconstruction_tree<std::min<int> >::g' will be initialized after [-Wreorder]
14 | vector<vector<int>> g;
| ^
werewolf.cpp:13:20: warning: 'std::vector<int> kruskal_reconstruction_tree<std::min<int> >::tin' [-Wreorder]
13 | vector<int> p, tin, tout;
| ^~~
werewolf.cpp:17:5: warning: when initialized here [-Wreorder]
17 | kruskal_reconstruction_tree(int n, int n0) : p(n), l(n0), g(n), tin(n), tout(n)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
76112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
76112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
440 ms |
143824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
76112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
