#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 15;
int p[MAXN];
int rang[MAXN];
vector <int> ans;
int need = -1;
int cntComp;
int GetPar(int v) {
if (p[v] == -1) {
return v;
}
return GetPar(p[v]);
}
void Comeback(int wasCnt, vector <tuple <int, int, int>> wasDSU) {
reverse(wasDSU.begin(), wasDSU.end());
cntComp = wasCnt;
for (auto [a, b, c] : wasDSU) {
p[a] = b;
rang[a] = c;
}
}
void Func(int l, int r, vector <tuple <int, int, int, int>> edges, vector <pair <int, int>> querys) {
int m = l + (r - l) / 2;
vector <tuple <int, int, int, int>> edgesL, edgesR;
vector <pair <int, int>> querysL, querysR;
vector <tuple <int, int, int>> wasDSU;
int wasCnt = cntComp;
for (auto [a, b, x, y] : edges) {
if (min(a, b) <= need && max(a, b) >= need + 1) {continue;}
if (x <= l && r <= y) {
a = GetPar(a);
b = GetPar(b);
if (a == b) {continue;}
wasDSU.emplace_back(a, p[a], rang[a]);
wasDSU.emplace_back(b, p[b], rang[b]);
if (rang[a] > rang[b]) {swap(a, b);}
--cntComp;
rang[b] += rang[a];
p[a] = b;
} else {
if (!(y < l || x > m)) {
edgesL.emplace_back(a, b, x, y);
}
if (!(m + 1 > y || r < x)) {
edgesR.emplace_back(a, b, x, y);
}
}
}
if (l == r) {
for (auto [pos, num] : querys) {
ans[num] = cntComp;
}
Comeback(wasCnt, wasDSU);
return;
}
for (auto [pos, num] : querys) {
if (pos <= m) {
querysL.emplace_back(pos, num);
} else {
querysR.emplace_back(pos, num);
}
}
Func(l, m, edgesL, querysL);
Func(m + 1, r, edgesR, querysR);
Comeback(wasCnt, wasDSU);
}
std::vector<int> simulateCollapse( int N, std::vector<int> T, std::vector<int> X, std::vector<int> Y, std::vector<int> W, std::vector<int> P) {
memset(p, -1, sizeof(p));
fill(rang, rang + MAXN, 1);
cntComp = N;
vector <tuple <int, int, int, int>> edges;
map <pair <int, int>, int> last;
ans.resize(W.size(), -1);
for (int i = 0; i < T.size(); ++i) {
int type = T[i], a = X[i], b = Y[i];
if (type == 1) {
last[{min(a, b), max(a, b)}] = i;
} else {
edges.emplace_back(a, b, last[{min(a, b), max(a, b)}], i - 1);
last.erase(last.find({min(a, b), max(a, b)}));
}
}
for (auto [x, y] : last) {
edges.emplace_back(x.first, x.second, y, T.size() - 1);
}
vector <pair <int, int>> querys(W.size());
for (int i = 0; i < W.size(); ++i) {
int w = W[i], p = P[i];
if (need == -1) {
need = p;
}
assert(need == p);
querys[i] = {w, i};
}
Func(0, T.size() - 1, edges, querys);
return ans;
}
Compilation message
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:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i < T.size(); ++i) {
| ~~^~~~~~~~~~
collapse.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int i = 0; i < W.size(); ++i) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1644 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
2284 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
4588 KB |
Output is correct |
| 2 |
Incorrect |
36 ms |
7328 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
4588 KB |
Output is correct |
| 2 |
Runtime error |
24 ms |
7660 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1644 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
2284 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
