#include "collapse.h"
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class UnionFind {
public:
vector<int> par;
void init(int sz) {
par.resize(sz, -1);
}
int root(int pos) {
if (par[pos] == -1) return pos;
par[pos] = root(par[pos]);
return par[pos];
}
void unite(int u, int v) {
u = root(u); v = root(v);
if (u == v) return;
par[u] = v;
}
bool same(int u, int v) {
if (root(u) == root(v)) return true;
return false;
}
};
const int Backet = 300;
int N, C, Q;
int T[100009], X[100009], Y[100009], W[100009], P[100009], num[100009], ans[100009];
vector<pair<int, int>> Edge;
UnionFind UF;
bool useda[100009], used[100009], usedb[100009];
void precise(int cl, int cr) {
int connectivity = N;
for (int i = 0; i <= 100000; i++) { used[i] = false; useda[i] = false; }
for (int i = 1; i < cl; i++) {
if (T[i] == 0) used[num[i]] = true;
if (T[i] == 1) used[num[i]] = false;
}
vector<int>vec;
for (int i = cl; i <= cr; i++) { useda[num[i]] = true; vec.push_back(num[i]); }
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
UF.init(N + 2);
for (int i = 0; i < Edge.size(); i++) {
if (used[i] == true && useda[i] == false) {
if (Edge[i].first <= P[1] && P[1] < Edge[i].second) {
if (UF.same(Edge[i].first, Edge[i].second) == false) connectivity--;
UF.unite(Edge[i].first, Edge[i].second);
}
}
}
for (int i = cl; i <= cr; i++) {
int pos1 = lower_bound(vec.begin(), vec.end(), num[i]) - vec.begin();
usedb[pos1] ^= true;
vector<int>E; vector<pair<int, int>>F;
for (int j = 0; j < vec.size(); j++) {
if (usedb[j] == false) continue;
int V = vec[j];
int u1 = Edge[V].first, u2 = Edge[V].second;
if (u1 <= P[1] && P[1] < u2) { E.push_back(u1); E.push_back(u2); F.push_back(make_pair(u1, u2)); }
}
sort(E.begin(), E.end());
E.erase(unique(E.begin(), E.end()), E.end());
UnionFind UF2; UF2.init(E.size()); int ret = connectivity;
for (int j = 0; j < F.size(); j++) {
int pos2 = lower_bound(E.begin(), E.end(), F[j].first) - E.begin();
int pos3 = lower_bound(E.begin(), E.end(), F[j].second) - E.begin();
if (UF2.same(pos2, pos3) == false) ret--;
UF2.unite(pos2, pos3);
}
ans[i] = ret;
}
}
vector<int> solve() {
for (int i = 1; i <= C; i++) Edge.push_back(make_pair(X[i], Y[i]));
sort(Edge.begin(), Edge.end());
Edge.erase(unique(Edge.begin(), Edge.end()), Edge.end());
for (int i = 1; i <= C; i++) num[i] = lower_bound(Edge.begin(), Edge.end(), make_pair(X[i], Y[i])) - Edge.begin();
for (int i = 1; i <= C; i += Backet) {
int el = i, er = i + Backet - 1; if (er > C) er = C;
precise(el, er);
}
vector<int> J;
for (int i = 1; i <= Q; i++) J.push_back(ans[W[i]]);
return J;
}
vector<int> simulateCollapse(int N1, vector<int>T1, vector<int>X1, vector<int>Y1, vector<int>W1, vector<int>P1) {
N = N1; C = T1.size(); Q = W1.size();
for (int i = 1; i <= C; i++) T[i] = T1[i - 1];
for (int i = 1; i <= C; i++) { X[i] = X1[i - 1]; X[i]++; }
for (int i = 1; i <= C; i++) { Y[i] = Y1[i - 1]; Y[i]++; }
for (int i = 1; i <= Q; i++) { W[i] = W1[i - 1]; W[i]++; }
for (int i = 1; i <= Q; i++) { P[i] = P1[i - 1]; P[i]++; }
for (int i = 1; i <= C; i++) { if (X[i] > Y[i]) swap(X[i], Y[i]); }
return solve();
}
Compilation message
collapse.cpp: In function 'void precise(int, int)':
collapse.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < Edge.size(); i++) {
~~^~~~~~~~~~~~~
collapse.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++) {
~~^~~~~~~~~~~~
collapse.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < F.size(); j++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
3956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
4084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
