#include "werewolf.h"
#include <bits/stdc++.h>
struct DSU {
std::vector<int> e;
void init(int n) {
e = std::vector<int>(n, -1);
}
int get(int x) {
return e[x] < 0 ? x : e[x] = get(e[x]);
}
bool same_set(int a, int b) {
return get(a) == get(b);
}
int size(int x) {
return -e[get(x)];
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) std::swap(x, y);
e[x] += e[y]; e[y] = x;
return true;
}
bool head(int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
e[y] = x;
return true;
}
};
struct LCAJump {
int n;
std::vector<std::vector<int>> par;
std::vector<std::vector<int>> adj;
std::vector<int> depth;
void init(int _n) {
n = _n;
int d = 1;
while ((1 << d) < n) d++;
par.assign(d, std::vector<int>(n));
adj.resize(n);
depth.resize(n);
}
void ae(int x, int y) {
adj[x].push_back(y);
adj[y].push_back(x);
}
void gen(int root = 0) {
par[0][root] = root;
dfs(root);
}
void dfs(int src = 0) {
for (int i = 1; i < par.size(); i++) {
par[i][src] = par[i - 1][par[i - 1][src]];
}
for (int nxt: adj[src]) {
if (nxt == par[0][src]) continue;
depth[nxt] = depth[par[0][nxt] = src] + 1;
dfs(nxt);
}
}
int jump(int x, int d) {
for (int i = 0; i < par.size(); i++) {
if ((d >> i) & 1) {
x = par[i][x];
}
}
return x;
}
int lca(int x, int y) {
if (depth[x] < depth[y]) std::swap(x, y);
x = jump(x, depth[x] - depth[y]);
if (x == y) return x;
for (int i = par.size() - 1; i >= 0; i--) {
int nx = par[i][x];
int ny = par[i][y];
if (nx != ny) x = nx, y = ny;
}
return par[0][x];
}
};
template <class T> struct SegTree {
const T ID = 1e9;
T comb(T a, T b) {
return std::min(a, b);
}
int n;
std::vector<T> seg;
void init(int _n) {
n = _n;
seg.assign(2 * n, ID);
}
void pull(int p) {
seg[p] = comb(seg[2 * p], seg[2 * p + 1]);
}
void upd(int p, T val) {
seg[p += n] = val;
for (p /= 2; p; p /= 2) pull(p);
}
void add(int p, T val) {
seg[p += n] += val;
for (p /= 2; p; p /= 2) pull(p);
}
T query(int l, int r) {
T ra = ID, rb = ID;
for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
if (l & 1) ra = comb(ra, seg[l++]);
if (r & 1) rb = comb(seg[--r], rb);
}
return comb(ra, rb);
}
};
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
using namespace std;
int Q = S.size();
int M = X.size();
vector<int> ans(Q);
vector<vector<int>> g1(N), g2(N);
DSU d1, d2; d1.init(N), d2.init(N);
vector<vector<int>> adj(N);
for (int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
LCAJump j1, j2;
j1.init(N), j2.init(N);
for (int i = 0; i < N; i++) {
for (int j : adj[i]) {
if (j > i || d1.same_set(i, j)) continue;
int u = i;
int v = d1.get(j);
g1[u].push_back(v);
g1[v].push_back(u);
d1.head(u, v);
j1.ae(u, v);;
}
}
for (int i = N - 1; i >= 0; i--){
for (int j : adj[i]) {
if (j < i || d2.same_set(i, j)) continue;
int u = i;
int v = d2.get(j);
g2[u].push_back(v);
g2[v].push_back(u);
d2.head(u, v);
j2.ae(u, v);;
}
}
int r1 = N - 1;
int r2 = 0;
vector<array<int, 2>> gap1(N), gap2(N);
vector<int> o1, o2;
int ti = 0;
function<int(int, int)> dfs1 = [&](int src, int par) -> int {
gap1[src][0] = gap1[src][1] = ti++;
o1.push_back(src);
for (int nxt : g1[src]) {
if (nxt == par) continue;
gap1[src][1] = max(gap1[src][1], dfs1(nxt, src));
}
return gap1[src][1];
};
function<int(int, int)> dfs2 = [&](int src, int par) -> int {
gap2[src][0] = gap2[src][1] = ti++;
o2.push_back(src);
for (int nxt : g2[src]) {
if (nxt == par) continue;
gap2[src][1] = max(gap2[src][1], dfs2(nxt, src));
}
return gap2[src][1];
};
dfs1(r1, -1);
ti = 0;
dfs2(r2, -1);
j1.gen(r1);
j2.gen(r2);
auto up = [&](int t, LCAJump& L, int src, int high) -> int {
for (int i = L.par.size() - 1; i >= 0; i--) {
if (t == 0) {
if (L.par[i][src] <= high) src = L.par[i][src];
} else {
if (L.par[i][src] >= high) src = L.par[i][src];
}
}
return src;
};
// map<int, int> conv;
// for (int i = 0; i < N; i++)
// conv[o1[i]] = i;
// vector<int> loc(N);
// cout << "STUFF" << endl;
// for (int i = 0; i < N; i++)
// cout << o1[i] << " ";
// cout << endl;
// for (int i = 0; i < N; i++)
// cout << o2[i] << " ";
// cout << endl << endl;
// for (int i = 0; i < N; i++)
// o1[i] = conv[o1[i]], o2[i] = conv[o2[i]], loc[o2[i]] = i;
// cout << "NEW STUFF" << endl;
// for (int i = 0; i < N; i++)
// cout << o1[i];
// cout << endl;
// for (int i = 0; i < N; i++)
// cout << o2[i];
// cout << endl << endl;
vector<vector<array<int, 4>>> lower(N);
for (int i = 0; i < Q; i++) {
int st = S[i];
int ed = E[i];
swap(st, ed);
int c1 = up(0, j1, st, R[i]);
int c2 = up(1, j2, ed, L[i]);
vector<int> oc(N);
for (int i = gap1[c1][0]; i <= gap1[c1][0]; i++)
oc[o1[i]]++;
for (int i = gap2[c2][0]; i <= gap2[c2][1]; i++)
oc[o2[i]]++;
bool ok = false;
for (int i = 0; i < N; i++)
ok |= (oc[i] > 1);
ans[i] = ok;
cout << "QUERY " << c1 << " " << c2 << endl;
// cout << "QUERY " << gap1[c1][0] << " " << gap1[c1][1] << " " << gap2[c2][0] << " " << gap2[c2][1] << endl;
// lower[gap1[c1][0]].push_back({gap1[c1][0], gap2[c2][0], gap2[c2][1], i});
}
// SegTree<int> seg;
// seg.init(N);
// for (int i = N - 1; i >= 0; i--) {
// seg.upd(loc[o2[i]], i);
// for (auto& qq : lower[i]) {
// if (seg.query(qq[1], qq[2]) <= qq[0]) ans[qq[3]] = 1;
// else ans[qq[3]] = 0;
// }
// }
// for (int x : ans) cout << x << '\n';
// cout << "MADE IT" << endl;
return ans;
}
Compilation message
werewolf.cpp: In member function 'void LCAJump::dfs(int)':
werewolf.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 1; i < par.size(); i++) {
| ~~^~~~~~~~~~~~
werewolf.cpp: In member function 'int LCAJump::jump(int, int)':
werewolf.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i = 0; i < par.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4067 ms |
108004 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
