#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include "collapse.h"
using namespace std;
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: In function 'void solve(std::vector<Q>)':
collapse.cpp:118:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0, j = 0, r = 0; i < s.size(); i++) {
~~^~~~~~~~~~
collapse.cpp:119:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < se1.size() && se1[j].x <= s[i].x) {
~~^~~~~~~~~~~~
collapse.cpp:135:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0, j = 0, r = 0; i < s.size(); i++) {
~~^~~~~~~~~~
collapse.cpp:136:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < se2.size() && se2[j].x > s[i].x) {
~~^~~~~~~~~~~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:203:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1152 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
4976 KB |
Output is correct |
| 2 |
Incorrect |
69 ms |
4860 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
4844 KB |
Output is correct |
| 2 |
Incorrect |
72 ms |
4844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1152 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
