#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;
#define LL long long
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define f first
#define s second
int N, M, Q;
vector<vector<int>> adj;
struct DSU {
vector<int> par, size, top;
bool topmax;
DSU(int N, bool mx){
par.resize(N); size.resize(N); top.resize(N);
for (int i = 0; i < N; ++i) {
size[i] = 1;
par[i] = i;
top[i] = i;
}
topmax = mx;
}
int find(int node) {
if (par[node] != node) {
par[node] = find(par[node]);
}
return par[node];
}
void merge(int A, int B) {
int rootA = find(A);
int rootB = find(B);
if (rootA == rootB) return;
top[rootA] = top[rootB] = topmax ? max(top[rootA], top[rootB]) : min(top[rootA], top[rootB]);
if (size[rootA] > size[rootB]) {
par[rootB] = rootA;
size[rootA] += size[rootB];
}
else {
par[rootA] = rootB;
size[rootB] += size[rootA];
}
}
};
struct MST {
vector<vector<int>> tree;
vector<int> lBound, rBound;
MST(vector<int> &input) {
tree.resize(4*input.size()+1);
lBound.resize(4*input.size()+1);
rBound.resize(4*input.size()+1);
build(0, 0, input.size()-1, input);
}
void build(int node, int L, int R, vector<int> &arr) {
lBound[node] = L; rBound[node] = R;
if (L == R) {
tree[node].pb(arr[L]); return;
}
build(2*node+1, L, (L+R)/2, arr); build(2*node+2, (L+R)/2+1, R, arr);
auto lptr = tree[2*node+1].begin(), rptr = tree[2*node+2].begin();
auto lend = tree[2*node+1].end(), rend = tree[2*node+2].end();
while(lptr != lend && rptr != rend) {
if (*lptr < *rptr) {
tree[node].pb(*lptr);
lptr++;
} else {
tree[node].pb(*rptr);
rptr++;
}
}
while(lptr != lend) {
tree[node].pb(*lptr);
lptr++;
}
while(rptr != rend) {
tree[node].pb(*rptr);
rptr++;
}
}
bool contains(int node, int dL, int dR) {
if (tree[node].back() < dL || tree[node].front() > dR) return false;
int min = -1, max = tree[node].size()-1;
while(max-min > 1) {
int mid = (min+max) >> 1;
if (tree[node][mid] >= dL) {
max = mid;
} else {
min = mid;
}
}
if (tree[node][max] <= dR) return true;
return false;
}
bool query(int node, int qL, int qR, int dL, int dR) {
if (qR < lBound[node] || qL > rBound[node]) return false;
if (qL <= lBound[node] && rBound[node] <= qR) {
return contains(node, dL, dR);
}
return query(2*node+1, qL, qR, dL, dR) || query(2*node+2, qL, qR, dL, dR);
}
};
vector<int> hstart, hend, wstart, wend;
int hpar[19][200005], wpar[19][200005];
vector<int> input;
void hdfs(int c, int p, vector<int> &heuler, vector<vector<int>> &hadj) {
hpar[0][c] = p;
hstart[c] = heuler.size();
heuler.pb(c);
for (int to : hadj[c]) {
hdfs(to, c, heuler, hadj);
}
hend[c] = heuler.size()-1;
}
int cwidx = 0;
void wdfs(int c, int p, vector<int> &widx, vector<vector<int>> &wadj) {
wpar[0][c] = p;
widx[c] = cwidx;
wstart[c] = cwidx;
cwidx++;
for (int to : wadj[c]) {
wdfs(to, c, widx, wadj);
}
wend[c] = cwidx-1;
}
void input_gen(int N, vector<int> &X, vector<int> &Y, vector<int> &S, vector<int> &E, vector<int> &L, vector<int> &R) {
vector<int> heuler, widx;
vector<vector<int>> hadj, wadj;
adj.resize(N+5);
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
adj[a].pb(b); adj[b].pb(a);
}
hadj.resize(N+5); wadj.resize(N+5);
widx.resize(N+5);
DSU h(N+5, false), w(N+5, true);
for (int i = N-1; i >= 0; i--) {
unordered_set<int> added;
for (int to : adj[i]) {
if (to > i) {
int root = h.find(to);
int rtop = h.top[root];
if (added.find(rtop) == added.end()) {
added.insert(rtop);
hadj[i].pb(rtop);
}
}
}
for (int val : added) h.merge(i, val);
}
for (int i = 0; i < N; i++) {
unordered_set<int> added;
for (int to : adj[i]) {
if (to < i) {
int root = w.find(to);
int rtop = w.top[root];
if (added.find(rtop) == added.end()) {
added.insert(rtop);
wadj[i].pb(rtop);
}
}
}
for (int val : added) w.merge(i, val);
}
hdfs(0, -1, heuler, hadj); wdfs(N-1, -1, widx, wadj);
input.resize(N);
for (int i = 0; i < N; i++) {
input[i] = widx[heuler[i]];
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
ios::sync_with_stdio(0);
cin >> N >> M >> Q;
hstart.resize(N+5); hend.resize(N+5);
wstart.resize(N+5); wend.resize(N+5);
input_gen(N, X, Y, S, E, L, R);
MST tree(input);
for (int i = 1; i <= 18; i++) {
for (int j = 0; j < N; j++) {
if (hpar[i-1][j] == -1) hpar[i][j] = -1;
else hpar[i][j] = hpar[i-1][hpar[i-1][j]];
if (wpar[i-1][j] == -1) wpar[i][j] = -1;
else wpar[i][j] = wpar[i-1][wpar[i-1][j]];
}
}
vector<int> ret;
for (int i = 0; i < Q; i++) {
int S, E, L, R;
cin >> S >> E >> L >> R;
if (S < L || E > R) {
cout << 0 << endl; continue;
}
for (int i = 18; i >= 0; i--) {
if (hpar[i][S] >= L) {
S = hpar[i][S];
}
if (wpar[i][E] != -1 && wpar[i][E] <= R) {
E = wpar[i][E];
}
}
ret.pb(tree.query(0, hstart[S], hend[S], wstart[E], wend[E]));
}
return ret;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
192 ms |
75660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
