#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.assign(n, 0);
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>, int> st;
for (int i = 0; i < m; ++i) {
pair<int, int> e = make_pair(from[i], to[i]);
if (type[i] == 0) {
st[e] = i;
} else {
assert(st.count(e));
go[st[e]] = i;
st.erase(e);
}
}
}
for (int i = 0; i < m; ++i) {
if (type[i] == 0 && go[i] == 0) {
go[i] = m;
}
}
vector<int> ans(q, 0);
for (int i = 0; i < q; ++i) {
int ncomp = n;
for (int j = 0; j < n; ++j) {
par[j] = j;
}
for (int j = 0; j < m; ++j) {
if (type[i] == 0 && j <= time[i] && time[i] < go[j]) {
if (to[j] <= pos[i] || from[j] > pos[i]) {
ncomp -= merge(from[j], to[j]);
}
}
}
ans[i] = ncomp;
}
return ans;
/*
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, n);
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);
}
}
}
{
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] -= 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] -= cnt2;
}
}
}
return ans;
*/
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
632 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
4352 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
4480 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
632 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
