Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "collapse.h"
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 100005;
- struct Event {
- int T, type, x, y;
- bool operator < (const Event& rhs) const {
- return (T == rhs.T) ? type < rhs.type : T < rhs.T;
- }
- };
- struct Edge {
- int id, u, v;
- bool operator < (const Edge& rhs) const {
- return u < rhs.u;
- }
- };
- int n;
- int par[N];
- int res[N];
- int f[2][N];
- int pos[N];
- bool state[N];
- bool iedge[N];
- bool inode[N];
- vector<Event> vec, buf;
- vector< pair<int, int> > dsu[2][500];
- map< pair<int, int>, int > label;
- vector<Edge> E1, E2;
- int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }
- bool join(int u, int v) {
- u = find(u), v = find(v);
- if (inode[u]) swap(u, v); // root prefer important node
- par[u] = v; return u != v;
- }
- void solve() {
- vector<int> vnode;
- vector<Edge> vedge;
- int cnt = 0;
- for (auto i : buf) {
- if (i.type < 0) {
- int id = label[{i.x, i.y}];
- if (!iedge[id]) {
- iedge[id] = 1;
- vedge.push_back({id, i.x, i.y});
- }
- if (!inode[i.x]) {
- inode[i.x] = 1, vnode.push_back(i.x);
- }
- if (!inode[i.y]) {
- inode[i.y] = 1, vnode.push_back(i.y);
- }
- }
- else pos[i.type] = cnt++;
- }
- {
- vector< pair<int, int> > vec1;
- for (auto i : buf) {
- if (i.type >= 0) vec1.push_back({i.x, i.type});
- }
- sort(vec1.begin(), vec1.end());
- for (int i = 0; i < n; ++i) par[i] = i;
- int ptr = 0, cur = 0, cnt = 0;
- for (auto i : vec1) {
- while (cur < i.first) ++cur, ++cnt;
- while (ptr < E1.size() && E1[ptr].u <= i.first) {
- if (!iedge[E1[ptr].id] && state[E1[ptr].id]) {
- cnt -= join(E1[ptr].u, E1[ptr].v);
- }
- ++ptr;
- }
- f[0][i.second] = cnt;
- for (auto j : vnode) {
- dsu[0][pos[i.second]].push_back({j, find(j)});
- }
- }
- }
- {
- vector< pair<int, int> > vec2;
- for (auto i : buf) {
- if (i.type >= 0) vec2.push_back({i.x + 1, i.type});
- }
- sort(vec2.begin(), vec2.end());
- reverse(vec2.begin(), vec2.end());
- for (int i = 0; i < n; ++i) par[i] = i;
- int ptr = 0, cur = 0, cnt = 0;
- for (auto i : vec2) {
- while (cur < n - i.first + 1) ++cur, ++cnt;
- while (ptr < E2.size() && E2[ptr].u >= i.first) {
- if (!iedge[E2[ptr].id] && state[E2[ptr].id]) {
- cnt -= join(E2[ptr].u, E2[ptr].v);
- }
- ++ptr;
- }
- f[1][i.second] = cnt;
- for (auto j : vnode) {
- dsu[1][pos[i.second]].push_back({j, find(j)});
- }
- }
- }
- for (auto i : buf) {
- if (i.type < 0) {
- int id = label[{i.x, i.y}];
- state[id] ^= 1; continue;
- }
- int id = i.type;
- for (int j = 0; j < 2; ++j) {
- for (auto k : dsu[j][pos[id]]) par[k.first] = k.second;
- for (auto k : vnode) {
- if (j == 0 && k > i.x || j == 1 && k <= i.x) continue;
- f[j][id] -= par[k] == k;
- }
- for (auto k : vedge) {
- // k.u < k.v
- if (state[k.id] && (k.v <= i.x || k.u > i.x)) join(k.u, k.v);
- }
- for (auto k : vnode) {
- if (j == 0 && k > i.x || j == 1 && k <= i.x) continue;
- f[j][id] += par[k] == k;
- }
- }
- res[id] = f[0][id] + f[1][id];
- }
- for (int i = 0; i < cnt; ++i) dsu[0][i].clear(), dsu[1][i].clear();
- for (auto i : buf) {
- if (i.type < 0) {
- iedge[label[{i.x, i.y}]] = inode[i.x] = inode[i.y] = 0;
- }
- }
- buf.clear();
- }
- vector<int> simulateCollapse(
- int _n,
- vector<int> T,
- vector<int> X,
- vector<int> Y,
- vector<int> W,
- vector<int> P
- ) {
- n = _n;
- int c = T.size();
- int q = W.size();
- for (int i = 0; i < c; ++i) {
- if (X[i] > Y[i]) swap(X[i], Y[i]);
- vec.push_back({i, -(T[i] + 1), X[i], Y[i]});
- }
- for (int i = 0; i < q; ++i) {
- vec.push_back({W[i], i, P[i], 0});
- }
- sort(vec.begin(), vec.end());
- int cnt = 0;
- for (int i = 0; i < c; ++i) {
- if (label[{X[i], Y[i]}]) continue;
- label[{X[i], Y[i]}] = ++cnt;
- E1.push_back({cnt, Y[i], X[i]});
- E2.push_back({cnt, X[i], Y[i]});
- }
- sort(E1.begin(), E1.end());
- sort(E2.begin(), E2.end());
- reverse(E2.begin(), E2.end());
- for (int i = 0; i < vec.size(); ++i) {
- buf.push_back(vec[i]);
- if (buf.size() == 365) solve();
- }
- if (buf.size()) solve();
- vector<int> vres;
- for (int i = 0; i < q; ++i) vres.push_back(res[i]);
- return vres;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement