| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 102196 | Minnakhmetov | Collapse (JOI18_collapse) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "collapse.h"
struct E {
int x, y, i;
bool operator < (const E &oth) const {
return x < oth.x;
}
};
struct Q {
int t, type, i, x;
bool operator < (const Q &oth) const {
return t == oth.t ? type : t < oth.t;
}
};
const int N = 1e5 + 5, Z = 350;
bool isOn[N], usedv[N], usede[N];
int par[N];
vector<E> edges, se1, se2;
map<pair<int, int>, int> mp_e;
vector<int> ans;
map<int, vector<pair<int, int>>> mp;
int n, m;
#define all(aaa) aaa.begin(), aaa.end()
int findSet(int v) {
return par[v] == v ? v : par[v] = findSet(par[v]);
}
bool un(int x, int y) {
x = findSet(x);
y = findSet(y);
if (x == y)
return false;
if (usedv[y])
swap(x, y);
par[y] = x;
return true;
}
void solve(vector<Q> qr) {
fill(usedv, usedv + N, false);
mp.clear();
vector<Q> s;
vector<E> ve;
vector<int> vtx;
for (Q q : qr) {
if (q.type) {
usede[q.i] = usedv[edges[q.i].x] =
usedv[edges[q.i].y] = 1;
}
else {
s.push_back(q);
}
}
for (int i = 0; i < n; i++) {
if (usedv[i]) {
vtx.push_back(i);
}
}
for (int i = 0; i < m; i++) {
if (usede[i]) {
ve.push_back(edges[i]);
}
}
sort(all(s), [](Q &a, Q &b) {
return a.x < b.x;
});
for (int i = 0; i < n; i++) {
par[i] = i;
}
for (int i = 0, j = 0, r = 0; i < s.size(); i++) {
while (j < se1.size() && se1[j].x <= s[i].x) {
if (!usede[se1[j].i] && isOn[se1[j].i])
r += un(se1[j].x, se1[j].y);
j++;
}
ans[s[i].i] -= r;
for (int k : vtx) {
if (k <= s[i].x)
mp[s[i].i].push_back({ k, findSet(k) });
}
}
for (int i = 0; i < n; i++) {
par[i] = i;
}
for (int i = 0, j = 0, r = 0; i < s.size(); i++) {
while (j < se2.size() && se2[j].x > s[i].x) {
if (!usede[se2[j].i] && isOn[se2[j].i])
r += un(se2[j].x, se2[j].y);
j++;
}
ans[s[i].i] -= r;
for (int k : vtx) {
if (k > s[i].x)
mp[s[i].i].push_back({ k, findSet(k) });
}
}
for (Q q : qr) {
if (q.type) {
isOn[q.i] ^= 1;
}
else {
for (auto p : mp[q.i])
par[p.first] = p.second;
for (E e : ve) {
if (isOn[e.i] &&
(e.x <= q.x || e.y > q.x)) {
ans[q.i] -= un(e.x, e.y);
}
}
}
}
}
vector<int> simulateCollapse(
int _n,
vector<int> T,
vector<int> X,
vector<int> Y,
vector<int> W,
vector<int> P
) {
n = _n;
m = T.size();
int q = W.size();
vector<Q> v;
for (int i = 0; i < m; i++) {
if (X[i] < Y[i])
swap(X[i], Y[i]);
if (!mp_e.count({ X[i], Y[i] })) {
mp_e[{X[i], Y[i]}] = edges.size();
edges.push_back({ X[i], Y[i], i });
}
se1.push_back({ X[i], Y[i], i });
se2.push_back({ Y[i], X[i], i });
v.push_back({ i, 1, mp_e[{X[i], Y[i]}] });
}
sort(all(se1));
sort(all(se2));
reverse(all(se2));
ans.resize(q, _n);
for (int i = 0; i < q; i++) {
v.push_back({ W[i], 0, i, P[i] });
}
sort(all(v));
for (int i = 0; i < v.size(); i++) {
if (i % Z == 0) {
solve(vector<Q>(v.begin() + i, v.begin() + min((int)v.size(), i + Z)));
}
}
return ans;
}