#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;
}
Compilation message
collapse.cpp:20:1: error: 'vector' does not name a type
vector<E> edges, se1, se2;
^~~~~~
collapse.cpp:21:1: error: 'map' does not name a type
map<pair<int, int>, int> mp_e;
^~~
collapse.cpp:22:1: error: 'vector' does not name a type
vector<int> ans;
^~~~~~
collapse.cpp:23:1: error: 'map' does not name a type
map<int, vector<pair<int, int>>> mp;
^~~
collapse.cpp: In function 'bool un(int, int)':
collapse.cpp:38:3: error: 'swap' was not declared in this scope
swap(x, y);
^~~~
collapse.cpp:38:3: note: suggested alternatives:
In file included from /usr/include/c++/7/vector:65:0,
from collapse.h:5,
from collapse.cpp:1:
/usr/include/c++/7/bits/stl_bvector.h:128:3: note: 'std::swap'
swap(bool& __x, _Bit_reference __y) noexcept
^~~~
In file included from /usr/include/c++/7/bits/stl_pair.h:59:0,
from /usr/include/c++/7/bits/stl_algobase.h:64,
from /usr/include/c++/7/vector:60,
from collapse.h:5,
from collapse.cpp:1:
/usr/include/c++/7/bits/move.h:187:5: note: 'std::swap'
swap(_Tp& __a, _Tp& __b)
^~~~
In file included from /usr/include/c++/7/exception:142:0,
from /usr/include/c++/7/new:40,
from /usr/include/c++/7/ext/new_allocator.h:33,
from /usr/include/x86_64-linux-gnu/c++/7/bits/c++allocator.h:33,
from /usr/include/c++/7/bits/allocator.h:46,
from /usr/include/c++/7/vector:61,
from collapse.h:5,
from collapse.cpp:1:
/usr/include/c++/7/bits/exception_ptr.h:166:5: note: 'std::__exception_ptr::swap'
swap(exception_ptr& __lhs, exception_ptr& __rhs)
^~~~
collapse.cpp: At global scope:
collapse.cpp:43:12: error: variable or field 'solve' declared void
void solve(vector<Q> qr) {
^~~~~~
collapse.cpp:43:12: error: 'vector' was not declared in this scope
collapse.cpp:43:12: note: suggested alternative:
In file included from /usr/include/c++/7/vector:64:0,
from collapse.h:5,
from collapse.cpp:1:
/usr/include/c++/7/bits/stl_vector.h:216:11: note: 'std::vector'
class vector : protected _Vector_base<_Tp, _Alloc>
^~~~~~
collapse.cpp:43:20: error: expected primary-expression before '>' token
void solve(vector<Q> qr) {
^
collapse.cpp:43:22: error: 'qr' was not declared in this scope
void solve(vector<Q> qr) {
^~
collapse.cpp:128:1: error: 'vector' does not name a type
vector<int> simulateCollapse(
^~~~~~
