#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
template<typename T, bool zero_indexing>
struct fenwick_tree {
int N;
vector<T> fen;
fenwick_tree(int n) {
N = n, fen.assign(n + 1, 0);
}
fenwick_tree(vector<T> a) {
N = a.size();
fen.assign(N + 1, 0);
for(int i = 0; i < N; ++i) {
add(i, a[i]);
}
}
void add(int p, T val) {
for(int i = p + zero_indexing;i <= N;i += i & -i) {
fen[i] += val;
}
}
void set(int p, T val) {
T set_val = val - query(p, p);
add(p, set_val);
}
T query(int l, int r) {
T ret = 0;
for(int i = r + zero_indexing; i >= 1; i -= i & -i) {
ret += fen[i];
}
for(int i = l + zero_indexing - 1; i >= 1; i -= i & -i) {
ret -= fen[i];
}
return ret;
}
};
const int N = 2e5 + 10;
int d[N], s1[N], s2[N], in1[N], in2[N], f1 = 0, f2 = 0;
vector<int> g1[N], g2[N];
int get(int a) {
return d[a] = (d[a] == a ? a : get(d[a]));
}
void dfs1(int u) {
s1[u] = 1;
in1[u] = f1++;
for(int v: g1[u]) {
dfs1(v);
s1[u] += s1[v];
}
}
void dfs2(int u) {
s2[u] = 1;
in2[u] = f2++;
for(int v: g2[u]) {
dfs2(v);
s2[u] += s2[v];
}
}
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
forn(i, N) d[i] = i;
int m = sz(x), q = sz(l);
vector<vector<int>> edges(n);
vector<int> root1(q), root2(q);
vector<int> ss[n + 5], ee[n + 5];
for(int i = 0;i < m; ++i) {
edges[x[i]].pb(y[i]);
edges[y[i]].pb(x[i]);
}
for(int i = 0;i < q; ++i) {
ss[l[i]].pb(i);
ee[r[i]].pb(i);
}
for(int i = n - 1; i >= 0; --i) {
set<int> st;
for(int v: edges[i]) {
if(v < i) continue;
st.insert(get(v));
}
for(auto x: st) {
g1[i].pb(x);
d[x] = i;
}
for(auto x: ss[i]) root1[x] = get(s[x]);
}
forn(i, N) d[i] = i;
for(int i = 0; i < n; ++i) {
set<int> st;
for(int v: edges[i]) {
if(v > i) continue;
st.insert(get(v));
}
for(auto x: st) {
g2[i].pb(x);
d[x] = i;
}
for(auto x: ee[i]) {
root2[x] = get(e[x]);
}
}
dfs1(0);
dfs2(n - 1);
for(int i = 0; i < n; ++i) {
assert(s1[i] > 0);
}
for(int i = n - 1; i >= 0; --i) {
assert(s2[i] > 0);
}
vector<int> revin(n);
for(int i = 0; i < n; ++i) {
revin[in1[i]] = i;
}
vector<int> event[n], noo[n];
for(int i = 0; i < q; ++i) {
int node = root1[i];
event[in1[node]].push_back(-1);
event[in1[node] + s1[node] - 1].push_back(i);
noo[in1[node] + s1[node] - 1].push_back(node);
}
vector<int> ans(q, 0);
fenwick_tree<int, 1> fen(N);
for(int i = 0; i < n; ++i) {
sort(all(event[i]));
for(auto x: event[i]) {
if(x < 0) {
fen.add(in2[revin[i]], 1);
} else {
int j = x;
int node = root2[j];
if(fen.query(in2[node], in2[node] + s2[node] - 1) > 0) {
ans[j] = 1;
cout << j << " " << ans[j] << "\n";
}
}
}
for(auto x: noo[i]) {
fen.add(in2[x], -1);
}
}
return ans;
}
/*
6 6 3
0 3
3 1
1 2
2 5
3 4
1 5
4 2 1 2
4 2 2 2
5 4 3 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
11220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
11220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
553 ms |
77876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
11220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
