#ifndef mikevui
// #include "task.h"
#endif // mikevui
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
template<typename T> bool maximize(T &x, const T &y) {
if (x < y) {x = y; return 1;}
return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
if (x > y) {x = y; return 1;}
return 0;
}
struct SMT{
int trsz;
vector<bool> tr;
void init(int n = 0) {
trsz = 1;
while (trsz < n) trsz <<= 1;
tr.assign(trsz<<1, 0);
}
void insval(int k, bool x) {
tr[k+trsz-1] = x;
}
void build() {
for (int i = trsz-1; i; i--) {
tr[i] = tr[i<<1]|tr[(i<<1)|1];
}
}
void update(int k, bool x) {
k += trsz - 1;
tr[k] = x;
k >>= 1;
while (k > 0) {
tr[k] = tr[k<<1]|tr[(k<<1)|1];
k >>= 1;
}
}
bool query(int l, int r) {
l += trsz - 1;
r += trsz;
bool res = 0;
while (l < r) {
if (l&1) res |= tr[l++];
if (r&1) res |= tr[--r];
l >>= 1;
r >>= 1;
}
return res;
}
void check() {
for (int i= 1; i <= trsz; i++) {
cout << query(i, i) << ' ';
}
cout << "\n";
}
};
struct query{
int s, l, id;
query(int _s, int _l, int _id){
s = _s;
l = _l;
id = _id;
}
};
const int maxn = 4e5+5, lg = 19;
int n, m, q;
vector<int> adj[maxn], ans, a[maxn];
vector<query> qu[maxn];
int tin2[maxn], tout2[maxn], h2[maxn], par2[maxn][lg+1], timer;
int pos[maxn], tin1[maxn], tout1[maxn], h1[maxn], par1[maxn][lg+1];
int sz[maxn], heavy[maxn];
SMT tr;
namespace dsu{
vector<int> dsu;
vector<bool> curon;
void init() {
dsu.assign(n+1, 0);
curon.assign(n+1, 0);
for (int i = 1; i <= n; i++) {
dsu[i] = i;
adj[i].clear();
}
}
int f(int u) {
if (u == dsu[u]) return u;
return dsu[u] = f(dsu[u]);
}
void addnode(int u) {
curon[u] = 1;
vector<int> roots;
for (int v : a[u]) {
if (curon[v]) {
roots.pb(f(v));
}
}
//the same like dsu tree on edges
sort(roots.begin(), roots.end());
roots.erase(unique(roots.begin(), roots.end()), roots.end());
for (int v : roots){
dsu[v] = u;
adj[u].pb(v);
}
}
}
void dfs2(int u) {
tin2[u] = ++timer;
//binlift
for (int j = 1; j <= lg; j++) {
par2[u][j] = par2[par2[u][j-1]][j-1];
}
for (int v : adj[u]) {
h2[v] = h2[u]+1;
par2[v][0] = u;
dfs2(v);
}
tout2[u] = timer;
}
void dfs1(int u){
sz[u] = 1;
tin1[u] = ++timer;
pos[timer] = u;
//binlift
for (int j = 1; j <= lg; j++) {
par1[u][j] = par1[par1[u][j-1]][j-1];
}
for (int v : adj[u]) {
h1[v] = h1[u]+1;
par1[v][0] = u;
dfs1(v);
sz[u] += sz[v];
}
tout1[u] = timer;
}
int binlift(int u, int bound, bool updo, int par[][lg+1], int h[]) {
//updo = 0 -> (1)
for (int j = lg; j >= 0; j--) {
while (MASK(j) < h[u] &&
((updo && par[u][j] >= bound) || (!updo && par[u][j] <= bound)))
u = par[u][j];
}
return u;
}
void dfssolve(int u, bool del = 0) {
//sack on (1) -> update 2
for (int v : adj[u]) {
if (heavy[u] == -1 || sz[v] > sz[heavy[u]]) {
heavy[u] = v;
}
}
for (int v : adj[u]) {
if (v == heavy[u]) continue;
dfssolve(v, 1);
}
if (heavy[u] != -1) {
dfssolve(heavy[u], 0);
}
//add u and light subtrees
for (int v : adj[u]) {
if (v == heavy[u]) continue;
for (int x = tin1[v]; x <= tout1[v]; x++) {
tr.update(tin2[pos[x]], 1);
}
}
tr.update(tin2[u], 1);
// cout << u << "\n";
// tr.check();
//solve queries at the same time -> query on (2)
for (int i = 0; i < (int)qu[u].size(); i++) {
int s = qu[u][i].s, l = qu[u][i].l, id = qu[u][i].id;
int node = binlift(s, l, 1, par2, h2);
ans[id] = tr.query(tin2[node], tout2[node]);
}
//del
if (del) {
for (int x = tin1[u]; x <= tout1[u]; x++) {
tr.update(tin2[pos[x]], 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) {
//normalize
n = N; m = X.size(); q = E.size();
for (int i = 0; i < m; i++) {
int u = X[i]+1, v = Y[i]+1;
a[u].pb(v);
a[v].pb(u);
}
//build dsu tree prefix (1), dsu tree suffix (2)
//(2) -> segment tree
dsu::init();
for (int i = n; i; i--) {
dsu::addnode(i);
}
//binlift
timer = 0;
h2[1] = 1;
memset(par2, 0, sizeof(par2));
dfs2(1);
//(1)
dsu::init();
for (int i = 1; i <= n; i++) {
dsu::addnode(i);
}
timer = 0;
h1[1] = 1;
memset(par1, 0, sizeof(par1));
dfs1(n);
//push queries
for (int i = 0; i < q; i++) {
int s = S[i]+1, t = E[i]+1, l = L[i]+1, r = R[i]+1;
int u = binlift(t, r, 0, par1, h1);
qu[u].pb(query(s, l, i));
}
//S -> (2), T -> (1)
//root: (1) -> n, (2) -> 1
tr.init(n);
memset(heavy, -1, sizeof(heavy));
ans.assign(q, 0);
dfssolve(n);
return ans;
}
#ifdef mikevui
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// #define name "task"
// if (fopen(name".inp", "r")) {
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
// }
int N, M, Q;
vector<int> X, Y, S, E, L, R;
cin >> N >> M >> Q;
for (int i= 0; i < M; i++) {
int x, y;
cin >> x >> y;
X.pb(x);
Y.pb(y);
}
for (int i= 0; i < Q; i++) {
int s, e, l, r;
cin >> s >> e >> l >> r;
S.pb(s);
E.pb(e);
L.pb(l);
R.pb(r);
}
vector<int> res = check_validity(N, X, Y, S, E, L, R);
for (int x : res) {
cout << x << ' ';
}
}
#endif // mikevui
/*
6 6 1
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
105296 KB |
Output is correct |
| 2 |
Correct |
14 ms |
105296 KB |
Output is correct |
| 3 |
Correct |
15 ms |
105360 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
105296 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
105296 KB |
Output is correct |
| 2 |
Correct |
14 ms |
105296 KB |
Output is correct |
| 3 |
Correct |
15 ms |
105360 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
105296 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
572 ms |
141120 KB |
Output is correct |
| 2 |
Correct |
409 ms |
148812 KB |
Output is correct |
| 3 |
Correct |
475 ms |
143176 KB |
Output is correct |
| 4 |
Incorrect |
439 ms |
140820 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
105296 KB |
Output is correct |
| 2 |
Correct |
14 ms |
105296 KB |
Output is correct |
| 3 |
Correct |
15 ms |
105360 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
105296 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
