/**
* Author : Nguyen Tuan Vu
* Created : 25.01.2023
**/
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
using namespace std;
mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}
const int MAXN = 4e5 + 5;
int n, m, nquery;
pair <int, int> edges[MAXN];
vector <int> adj[MAXN];
struct QUERY {
int s, t, l, r;
// constraints :
// For each query i : 0 <= i < Q
// 0 <= l(i) <= s(i) <= n - 1
// 0 <= e(i) <= r(i) <= n - 1
// s(i) != e(i)
// l(i) <= r(i)
QUERY() {}
QUERY(int s, int t, int l, int r) {
this->s = s;
this->t = t;
this->l = l;
this->r = r;
}
} q[MAXN];
namespace sub2 {
int dd[2][MAXN], cur;
void dfs(int type, int u, int i) {
if (dd[type][u] == cur) return;
//cout << u << ' ' << trans << '\n';
dd[type][u] = cur;
for (auto v : adj[u]) {
if (type == 0 && v >= q[i].l) {
dfs(type, v, i);
}
if (type == 1 && v <= q[i].r) {
dfs(type, v, i);
}
}
}
vector <int> solve() {
vector <int> tmp;
FOR(i, 1, nquery) {
++cur;
dfs(0, q[i].s, i);
dfs(1, q[i].t, i);
bool ok = 0;
REP(j, n) if (dd[0][j] == cur && dd[1][j] == cur) {
ok = 1;
break;
}
if (ok) tmp.push_back(1);
else tmp.push_back(0);
}
return tmp;
}
};
namespace sub3 {
bool check() {
if (m != n - 1) return false;
int cnt2 = 0, cnt1 = 0;
REP(i, n) {
if (adj[i].size() != 1 && adj[i].size() != 2) return false;
if (adj[i].size() == 2) cnt2++;
else cnt1++;
}
return (cnt1 == 2 && cnt2 == n - 2);
}
int pos[MAXN], a[MAXN], pMin[MAXN][20], pMax[MAXN][20];
vector <int> solve() {
int root = 0, pre = -1;
REP(i, n) if (adj[i].size() == 1) {
root = i;
break;
}
n = 0;
while (1) {
a[++n] = root;
bool ok = 0;
for (auto x : adj[root]) if (x == pre) {
continue;
}
else {
pre = root;
root = x;
ok = 1;
break;
}
if (ok == 0) break;
}
//cout << n << '\n';
//FOR(i, 1, n) cout << a[i] << " \n"[i == n];
auto log2 = [&] (int x) {
return 31 - __builtin_clz(x);
};
FOR(i, 1, n) {
pos[a[i]] = i;
pMin[i][0] = pMax[i][0] = a[i];
}
FOR(i, 1, log2(n)) FOR(j, 1, n - MASK(i) + 1) {
pMin[j][i] = min(pMin[j][i - 1], pMin[j + MASK(i - 1)][i - 1]);
pMax[j][i] = max(pMax[j][i - 1], pMax[j + MASK(i - 1)][i - 1]);
}
auto getMin = [&] (int l, int r) {
int k = log2(r - l + 1);
return min(pMin[l][k], pMin[r - MASK(k) + 1][k]);
};
auto getMax = [&] (int l, int r) {
int k = log2(r - l + 1);
return max(pMax[l][k], pMax[r - MASK(k) + 1][k]);
};
vector <int> tmp;
FOR(i, 1, nquery) {
//cout << q[i].s << ' ' << q[i].t << ' ';
//cout << pos[q[i].s] << ' ' << pos[q[i].t] << '\n';
if (pos[q[i].s] < pos[q[i].t]) {
//cout << "*";
int l = pos[q[i].s] - 1, r = pos[q[i].t] + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (getMin(pos[q[i].s], mid) >= q[i].l) l = mid;
else r = mid;
}
int L = pos[q[i].s] - 1, R = pos[q[i].t] + 1;
while (R - L > 1) {
int mid = (L + R) >> 1;
if (getMax(mid, pos[q[i].t]) <= q[i].r) R = mid;
else L = mid;
}
if (R <= l) tmp.push_back(1);
else tmp.push_back(0);
}
else {
int l = pos[q[i].t] - 1, r = pos[q[i].s] + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (getMax(pos[q[i].t], mid) <= q[i].r) l = mid;
else r = mid;
}
int L = pos[q[i].t] - 1, R = pos[q[i].s] + 1;
while (R - L > 1) {
int mid = (L + R) >> 1;
if (getMin(mid, pos[q[i].s]) >= q[i].l) R = mid;
else L = mid;
}
if (R <= l) tmp.push_back(1);
else tmp.push_back(0);
}
}
return tmp;
}
};
namespace sub4 {
vector <int> line[MAXN], adj2[MAXN];
int par[MAXN], tin[2][MAXN], tout[2][MAXN], cnt, node[MAXN];
vector <int> it[MAXN << 2];
void dfs(int u, int type) {
tin[type][u] = ++cnt;
for (auto v : adj2[u]) {
dfs(v, type);
}
tout[type][u] = cnt;
}
#define left mid << 1, l, mid
#define right mid << 1 | 1, mid + 1, r
int get_root(int u) {return (par[u] < 0 ? u : par[u] = get_root(par[u]));}\
void build(int i = 1, int l = 1, int r = n) {
if (l == r) {
it[i].push_back(node[i]);
return;
}
int mid = (l + r) >> 1;
build(left); build(right);
it[i].resize(it[i << 1].size() + it[i << 1 | 1].size());
merge(ALL(it[i << 1]), ALL(it[i << 1 | 1]), it[i].begin());
}
bool check(int u, int v, int borderL, int borderR, int i = 1, int l = 1, int r = n) {
if (l > v || r < u) return 0;
if (u <= l && r <= v) {
auto jt = lower_bound(ALL(it[i]), borderL);
if (jt == it[i].end()) return 0;
return (*jt <= borderR);
}
int mid = (l + r) >> 1;
if (check(u, v, borderL, borderR, left)) return 1;
return check(u, v, borderL, borderR, right);
}
vector <int> solve() {
FOR(i, 1, nquery) line[q[i].l].push_back(i);
memset(par, -1, sizeof par);
FORD(u, n - 1, 0) {
for (auto v : adj[u]) if (v > u) {
v = get_root(v);
if (v != u) {
par[v] = u;
adj2[u].push_back(v);
}
}
for (auto i : line[u]) {
q[i].s = get_root(q[i].s);
}
}
//REP(i, n) {
//for (auto v : adj2[i]) cout << v << ' ';
//cout << '\n';
//}
dfs(0, 0);
//REP(i, n) cout << tin[0][i] << " \n"[i == n - 1];
//cout << "*";
//return vector <int> (n, 0);
memset(par, -1, sizeof par);
FOR(i, 0, n - 1) line[i].clear(), adj2[i].clear();
FOR(i, 1, nquery) line[q[i].r].push_back(i);
FOR(u, 0, n - 1) {
for (auto v : adj[u]) if (v < u) {
v = get_root(v);
if (v != u) {
par[v] = u;
adj2[u].push_back(v);
}
}
for (auto i : line[u]) {
q[i].t = get_root(q[i].t);
}
}
cnt = 0;
dfs(n - 1, 1);
REP(i, n) node[tin[0][i]] = tin[1][i];
//return vector <int> (nquery, 0);
build();
//return vector <int> (nquery, 0);
vector <int> tmp;
FOR(i, 1, nquery) {
tmp.push_back(check(tin[0][q[i].s], tout[0][q[i].s], tin[1][q[i].t], tout[1][q[i].t]));
}
return tmp;
}
};
vector <int> check_validity(int N, vector <int> X, vector <int> Y, vector <int> S, vector <int> T, vector <int> L, vector <int> R) {
n = N; m = X.size(); nquery = S.size();
REP(i, m) {
edges[i + 1] = make_pair(X[i], Y[i]);
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
REP(i, nquery) q[i + 1] = QUERY(S[i], T[i], L[i], R[i]);
return sub4::solve();
if (n <= 3000 && m <= 6000 && nquery <= 3000) return sub2::solve();
else if (sub3::check()) return sub3::solve();
else return sub4::solve();
return vector <int> (nquery, 0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
67656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
67656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
514 ms |
111088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
67656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
