#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
vector<int> par;
vector<int> par2;
vector<int> last;
int tt;
int find(int u) {
if (par[u] == u) {
return u;
} else {
return par[u] = find(par[u]);
}
}
bool merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) {
return false;
} else {
par[v] = u;
return true;
}
}
int find2(int u) {
if (last[u] != tt) {
last[u] = tt;
par2[u] = par[u];
}
if (par2[u] == u) {
return u;
} else {
return par2[u] = find2(par2[u]);
}
}
bool merge2(int u, int v) {
u = find2(u);
v = find2(v);
if (u == v) {
return true;
} else {
par2[v] = u;
return true;
}
}
vector<int> simulateCollapse(int n, vector<int> type, vector<int> from, vector<int> to, vector<int> time, vector<int> pos) {
int m = type.size();
int q = time.size();
par.resize(n);
par2.resize(n);
last.resize(n);
for (int i = 0; i < m; ++i) {
if (from[i] > to[i]) {
swap(from[i], to[i]);
}
}
vector<int> go(m);
{
map<pair<int, int>, vector<int>> st;
for (int i = 0; i < m; ++i) {
auto e = make_pair(from[i], to[i]);
if (type[i] == 0) {
st[e].emplace_back(i);
} else {
go[st[e].back()] = i;
st[e].pop_back();
}
}
}
for (int i = 0; i < m; ++i) {
if (type[i] == 0 && go[i] == 0) {
go[i] = m;
}
}
vector<int> pref, suf;
for (int i = 0; i < m; ++i) {
if (type[i] == 0) {
pref.emplace_back(i);
suf.emplace_back(i);
}
}
sort(pref.begin(), pref.end(), [&](int u, int v) {
return to[u] < to[v];
});
sort(suf.begin(), suf.end(), [&](int u, int v) {
return from[u] > from[v];
});
vector<vector<int>> qs(n);
for (int i = 0; i < q; ++i) {
qs[pos[i]].emplace_back(i);
}
vector<int> ans(q);
int block = 320;
for (int l = 0; l < m; l += block) {
int r = min(m, l + block);
vector<int> pref_all;
vector<int> suf_all;
vector<int> pref_cand;
vector<int> suf_cand;
for (int id : pref) {
if (id <= l && r <= go[id]) {
pref_all.emplace_back(id);
} else if (id < r && l < go[id]) {
pref_cand.emplace_back(id);
}
}
for (int id : suf) {
if (id <= l && r <= go[id]) {
suf_all.emplace_back(id);
} else if (id < r && l < go[id]) {
suf_cand.emplace_back(id);
}
}
vector<int> pref_qs;
vector<int> suf_qs;
for (int i = 0; i < n; ++i) {
for (int id : qs[i]) {
if (l <= time[id] && time[id] < r) {
pref_qs.emplace_back(id);
}
}
}
for (int i = n - 1; i >= 0; --i) {
for (int id : qs[i]) {
if (l <= time[id] && time[id] < r) {
suf_qs.emplace_back(id);
}
}
}
assert(pref_all.size() == suf_all.size());
assert(pref_cand.size() == suf_cand.size());
assert(pref_qs.size() == suf_qs.size());
{
for (int i = 0; i < n; ++i) {
par[i] = i;
}
int ptr = 0;
int cnt = 0;
for (int id : pref_qs) {
while (ptr < pref_all.size() && to[pref_all[ptr]] <= pos[id]) {
cnt += merge(from[pref_all[ptr]], to[pref_all[ptr]]);
++ptr;
}
int cnt2 = cnt;
++tt;
for (int jd : pref_cand) {
if (jd <= time[id] && time[id] < go[jd] && to[jd] <= pos[id]) {
cnt2 += merge2(from[jd], to[jd]);
}
}
ans[id] += (pos[id] + 1 - cnt2);
}
}
{
for (int i = 0; i < n; ++i) {
par[i] = i;
}
int ptr = 0;
int cnt = 0;
for (int id : suf_qs) {
while (ptr < suf_all.size() && from[suf_all[ptr]] > pos[id]) {
cnt += merge(from[suf_all[ptr]], to[suf_all[ptr]]);
++ptr;
}
int cnt2 = cnt;
++tt;
for (int jd : suf_cand) {
if (jd <= time[id] && time[id] < go[jd] && from[jd] > pos[id]) {
cnt2 += merge2(from[jd], to[jd]);
}
}
ans[id] += (n - 1 - pos[id] - cnt2);
}
}
}
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:146:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr < pref_all.size() && to[pref_all[ptr]] <= pos[id]) {
~~~~^~~~~~~~~~~~~~~~~
collapse.cpp:167:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr < suf_all.size() && from[suf_all[ptr]] > pos[id]) {
~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
640 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
3832 KB |
Output is correct |
| 2 |
Correct |
32 ms |
3832 KB |
Output is correct |
| 3 |
Incorrect |
566 ms |
5872 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
3832 KB |
Output is correct |
| 2 |
Incorrect |
34 ms |
3844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
640 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
