이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define REB(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 2e5 + 7;
const int N2 = 4e5 + 7;
const int Mod = 1e9 + 7;///lon
const ll INF = 1e18 + 7;
const int BASE = 137;
const int szBL = 350;
struct Query {
int S, T, L, R;
};
struct Data {
int L, R, L2, R2;
};
int n, m, Q;
vector<int> ke[N];
Query qr[N];
vector<int> events[N];
///KRT
int root;
int ein[N2], eout[N2];
vector<int> adj[N2];
int S[N2], T[N2];
pii RangeS[N2], RangeT[N2];
int Ans[N];
int inS[N2];
vector<pii> events_in_T[N2];
struct Disjoin_set {
int nNode;
int lab[N2];
void init (int n) {
rep (i, 1, n) {
lab[i] = i;
}
nNode = n;
}
int Find (int u) {
return u == lab[u] ? u : lab[u] = Find(lab[u]);
}
void Join (int u, int v, int typ) {
u = Find(u);
v = Find(v);
if (u == v)
return;
++nNode;
if (typ == 1) {
adj[nNode].pb(v);
adj[nNode].pb(u);
}
lab[u] = lab[v] = lab[nNode] = nNode;
}
}DSU;
struct Fenwick_Tree {
int m;
int fen[N2];
void init (int n) {
m = n;
}
void update (int pos, int val) {
for (; pos <= m; pos += pos & -pos) fen[pos] += val;
}
int get (int pos) {
int res = 0;
for (;pos > 0; pos -= pos & -pos) res += fen[pos];
return res;
}
int get (int L, int R) {
return get(R) - get(L - 1);
}
}BIT;
vector<int> process () {
// cin >> n >> m >> Q;
// rep (i, 1, m) {
// int u, v;
// cin >> u >> v;
// ++u, ++v;
// ke[u].pb(v);
// ke[v].pb(u);
// }
// rep (i, 1, Q) {
// cin >> qr[i].S >> qr[i].T >> qr[i].L >> qr[i].R;
// ++qr[i].S, ++qr[i].T, ++qr[i].L, ++qr[i].R;
// }
rep (i, 1, n) vector<int> ().swap(events[i]);
rep (i, 1, Q) {
events[qr[i].L].pb(i);
}
///make_Tree1
{
DSU.init(n);
rep (i, 1, n) vector<int> ().swap(adj[i]);
REB (u, n, 1) {
iter (&v, ke[u]) {
if (v >= u) DSU.Join(u, v, 1);
}
}
root = DSU.Find(1);
int time_dfs = 0;
function<void(int, int)> pdfs = [&] (int u, int p) {
ein[u] = ++time_dfs;
S[ein[u]] = u;
iter (&v, adj[u]) {
if (v != p) {
pdfs(v, u);
}
}
eout[u] = time_dfs;
};
pdfs(root, 0);
}
DSU.init(n);
REB (u, n, 1) {
iter (&v, ke[u]) {
if (v >= u) DSU.Join(u, v, 0);
}
iter (&id, events[u]) {
int Anc = DSU.Find(qr[id].S);
RangeS[id] = {ein[Anc], eout[Anc]};
}
}
rep (i, 1, n) vector<int> ().swap(events[i]);
rep (i, 1, Q) {
events[qr[i].R].pb(i);
}
///make_Tree2
{
DSU.init(n);
rep (i, 1, 2 * n) vector<int> ().swap(adj[i]);
rep (u, 1, n) {
iter (&v, ke[u]) {
if (v <= u) DSU.Join(u, v, 1);
}
}
root = DSU.Find(1);
int time_dfs = 0;
function<void(int, int)> pdfs = [&] (int u, int p) {
ein[u] = ++time_dfs;
T[ein[u]] = u;
iter (&v, adj[u]) {
if (v != p) {
pdfs(v, u);
}
}
eout[u] = time_dfs;
};
pdfs(root, 0);
}
DSU.init(n);
rep (u, 1, n) {
iter (&v, ke[u]) {
if (v <= u) DSU.Join(u, v, 0);
}
iter (&id, events[u]) {
int Anc = DSU.Find(qr[id].T);
RangeT[id] = {ein[Anc], eout[Anc]};
}
}
// rep (i, 1, 2 * n) cout << S[i]<<" \n"[i == 2 *n];
// rep (i, 1, 2 * n) cout << T[i]<<" \n"[i == 2 *n];
// rep (i, 1, Q) cout << RangeS[i].fs <<","<<RangeS[i].se<<" "<<RangeT[i].fs <<","<<RangeT[i].se<<"\n";
///calc
rep (i, 1, 2 * n) if (S[i] <= n && S[i] >= 1) inS[S[i]] = i;
rep (i, 1, Q) {
events_in_T[RangeT[i].fs - 1].pb({i, -1});
events_in_T[RangeT[i].se].pb({i, 1});
}
BIT.init(2 * n);
rep (i, 1, 2 * n) {
if (T[i] <= n && T[i] >= 1) BIT.update(inS[T[i]], 1);
iter (&id, events_in_T[i]) {
int idx = id.fs, sign = id.se;
int L, R;
tie(L, R) = RangeS[idx];
Ans[idx] += sign * BIT.get(L, R);
}
}
vector<int> res;
rep (i, 1, Q) {
res.pb(Ans[i] > 0);
// cout << Ans[i]<<"\n";
}
return res;
}
vector<int> check_validity(int _n, vector<int> X, vector<int> Y, vector<int> _S, vector<int> _E, vector<int> _L, vector<int> _R) {
n = _n;
m = SZ(X);
rep (i, 1, m) {
int u = X[i - 1], v = Y[i - 1];
++u, ++v;
ke[u].pb(v);
ke[v].pb(u);
}
Q = SZ(_S);
rep (i, 1, Q) {
qr[i].S = _S[i - 1];
qr[i].T = _E[i - 1];
qr[i].L = _L[i - 1];
qr[i].R = _R[i - 1];
++qr[i].S, ++qr[i].T, ++qr[i].L, ++qr[i].R;
}
return process();
}
//#define file(name) if(fopen(name".inp","r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
//main () {
// vector<int> cur = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2}, {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
// iter (&id, cur) cout << id <<"\n";
//// file("c");
// ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
// int num_Test = 1;
//// cin >> num_Test;
// while (num_Test--) {
// process();
// }
//}
/*
onepunch +25
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
xử lí khéo hay
cận trên để giảm không gian và thời gian của mô hình bài toán
cận dưới để có thêm insight về kết quả bài toán
gọi sao cho có lợi cho mình nhất
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |