#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
struct DSU {
vi e, mi, ma;
DSU(int n) : e(n, -1), mi(n), ma(n) {
iota(mi.begin(), mi.end(), 0);
iota(ma.begin(), ma.end(), 0);
}
int repr(int u) {
while(e[u] >= 0) u = e[u];
return u;
}
bool join(int u, int v) {
u = repr(u);
v = repr(v);
if(u == v) return false;
if(e[u] >= e[v]) swap(u, v);
mi[u] = min(mi[u], mi[v]);
ma[u] = max(ma[u], ma[v]);
e[u] += e[v];
e[v] = u;
return true;
}
bool same(int u, int v) {
return repr(u) == repr(v);
}
ii seg(int u) {
u = repr(u);
return make_pair(mi[u], ma[u]);
}
};
struct AIB {
int n;
vi V;
AIB(int N) : n(N + 1), V(N + 1, 0) {}
void update(int p, int v) {
++p;
while(p < n) {
V[p] += v;
p += p & -p;
}
}
int query(int p) {
++p;
int re = 0;
while(p) {
re += V[p];
p -= p & -p;
}
return re;
}
};
struct treeE {
int n;
int tmr = 0;
vi par, in, out;
vector<vi> G;
vector<set<int> > Tmp;
vector<vi> Anc;
AIB Sol;
treeE(int N, vector<vi> &G0) : n(N), par(N, -1), in(N),
out(N), G(G0), Tmp(N), Sol(N) {
function<void(int, int)> dfs0 = [&](int u, int p) {
par[u] = p;
for(auto it : G[u]) {
dfs0(it, u);
}
};
dfs0(N - 1, -1);
function<void(int)> dfs2 = [&](int u) {
in[u] = out[u] = tmr++;
for(auto it : G[u]) dfs2(it);
out[u] = tmr;
};
dfs2(N - 1);
Anc.push_back(par);
for(int k = 1; (1 << k) <= n; ++k) {
Anc.push_back(Anc.back());
for(int i = 0; i < n; ++i) {
if(Anc[k][i] == -1) continue;
Anc[k][i] = Anc[k - 1][Anc[k - 1][i]];
}
}
}
void activate(int u, int id) {
Tmp[u].insert(id);
Sol.update(in[u], 1);
}
void disable(int u, int id) {
Tmp[u].erase(id);
Sol.update(in[u], -1);
}
ii find_active(int u) { /// {nod, id}
int v = Sol.query(in[u]);
if(!v) return {-1, -1};
for(int k = int(Anc.size()) - 1; k >= 0; --k) {
if(Anc[k][u] != -1 && Sol.query(in[Anc[k][u]]) == v) u = Anc[k][u];
}
return {u, *Tmp[u].begin()};
}
};
struct treeS {
int n;
vector<vi> G;
treeS(int N, vector<vi> &G0) : n(N), G(G0) {}
vi solve(treeE &TE, vi S, vi E) {
int q = (int)S.size();
vi Re(q, 0);
set<int> Active;
vector<vi> MarkS(n);
for(int i = 0; i < q; ++i) {
MarkS[S[i]].push_back(i);
}
function<void(int)> dfs = [&](int u) {
for(auto it : MarkS[u]) {
Active.insert(it);
TE.activate(E[it], it);
}
//fac verificarea de valoare
int nod, id;
while(1) {
tie(nod, id) = TE.find_active(u); /// aka, valoarea u
if(nod == -1) break;
else {
Active.erase(id);
TE.disable(E[id], id);
Re[id] = 1;
}
}
for(auto it : G[u]) {
dfs(it);
}
for(auto it : MarkS[u]) {
if(Active.count(it)) {
Active.erase(it);
TE.disable(E[it], it);
}
}
};
dfs(0);
return Re;
}
};
struct BinLift {
int n;
vector<vi> A;
BinLift(vi V) {
n = int(V.size());
A.push_back(V);
for(int k = 1; (1 << k) <= n; ++k) {
A.push_back(A.back());
for(int i = 0; i < n; ++i)
if(A[k - 1][i] < 0 || A[k - 1][i] >= n);
else A[k][i] = A[k - 1][A[k - 1][i]];
}
}
int lift(int u, int k) {
return A[k][u];
}
};
vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R) {
int q = (int)S.size(), m = (int)X.size();
vector<vi> Lg(n);
for(int i = 0; i < m; ++i) {
Lg[X[i]].push_back(Y[i]);
Lg[Y[i]].push_back(X[i]);
}
DSU St(n);
vi GEpar(n, n), GSpar(n, -1);
vector<vi> GE(n), GS(n);
for(int i = 0; i < n; ++i) {
for(auto it : Lg[i])
if(it < i) {
auto [mi, ma] = St.seg(it);
if(St.join(it, i)) {
GE[i].push_back(ma);
GEpar[ma] = i;
}
}
}
DSU Dr(n);
for(int i = n - 1; i >= 0; --i) {
for(auto it : Lg[i]) {
if(it > i) {
auto [mi, ma] = Dr.seg(it);
if(Dr.join(it, i)) {
GS[i].push_back(mi);
GSpar[mi] = i;
}
}
}
}
vector<vi> G(n);
for(int i = 0; i < n; ++i) {
copy(GS[i].begin(), GS[i].end(), back_inserter(G[i]));
for(auto it : GE[i])
G[it].push_back(i);
}
BinLift BLS(GSpar), BLE(GEpar);
auto reprS = [&](int u, int lim) {
for(int k = int(BLS.A.size()) - 1; k >= 0; --k)
if(BLS.lift(u, k) >= lim) u = BLS.lift(u, k);
return u;
};
auto reprE = [&](int u, int lim) {
for(int k = int(BLE.A.size()) - 1; k >= 0; --k)
if(BLE.lift(u, k) <= lim) u = BLE.lift(u, k);
return u;
};
for(int nr = 0; nr < q; ++nr) {
S[nr] = reprS(S[nr], L[nr]);
E[nr] = reprE(E[nr], R[nr]);
}
treeS TGS(n, GS);
treeE TGE(n, GE);
return TGS.solve(TGE, S, E);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4073 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4073 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4053 ms |
146688 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4073 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
