#include <bits/stdc++.h>
#include "collapse.h"
#define pb push_back
#define fi first
#define se second
using namespace std;
const int blocksz = 300;
struct query {
int plan_day, collapse_town, id;
query(int x, int y, int z) {plan_day = x; collapse_town = y; id = z;}
};
bool cmpquery(query A, query B) {return A.plan_day < B.plan_day;}
struct operation {
int u, v, sz_u, sz_v;
operation(int x, int y, int z, int d) {u = x; v = y; sz_u = z; sz_v = d;}
};
vector <int> sz, p;
vector <operation> op;
int sz_comp;
void make_set(int n) {
sz.assign(n, 1); p.assign(n, 0); op.clear();
for (int i = 0; i < n; i++) p[i] = i;
sz_comp = n;
}
int getp(int u) {
if (p[u] == u) return u;
return getp(p[u]);
}
int add(int u, int v) {
u = getp(u); v = getp(v);
if (u == v) return 0;
if (sz[u] > sz[v]) swap(u, v);
op.pb({u, v, sz[u], sz[v]});
p[u] = v;
sz[v] += sz[u];
sz_comp--;
return 1;
}
void go_back() {
operation opp = op[op.size() - 1];
int u = opp.u, v = opp.v, sz_u = opp.sz_u, sz_v = opp.sz_v;
p[u] = u; p[v] = v; sz[u] = sz_u; sz[v] = sz_v;
sz_comp++;
op.pop_back();
}
vector <int> simulateCollapse(int n, vector <int> t, vector <int> x, vector <int> y, vector <int> w, vector <int> p) {
int c = t.size(), q = w.size(), m = 0;
vector <query> qu; qu.clear();
for (int i = 0; i < q; i++) {
qu.pb({w[i], p[i], i});
}
sort(qu.begin(), qu.end(), cmpquery);
vector <int> refer, state, vis; refer.assign(c, 0);
vector <pair<int, int>> edges; edges.clear();
map <pair<int, int>, int> edge_id; edge_id.clear();
for (int i = 0; i < c; i++) {
if (x[i] > y[i]) swap(x[i], y[i]);
if (!edge_id.count({x[i], y[i]})) edge_id[{x[i], y[i]}] = m++, edges.pb({x[i], y[i]});
refer[i] = edge_id[{x[i], y[i]}];
}
state.assign(m, 0);
vector <vector<int>> min_v, max_v, qus_v; min_v.assign(n, {}); max_v.assign(n, {}); qus_v.assign(n, {});
vector <int> ans; ans.assign(q, 0);
int curblock = 0, prv = -1;
// for (int i = 0; i < m; i++) {
// cout << i << " " << edges[i].fi << " " << edges[i].se << endl;
// }
// for (int i = 0; i < c; i++) {
// cout << t[i] << " " << x[i] << " " << y[i] << " " << refer[i] << endl;
// }
// for (int i = 0; i < q; i++)
// cout << qu[i].plan_day << " " << qu[i].collapse_town << " " << qu[i].id << endl;
// cout << endl;
while (true) {
int l = curblock * blocksz, r = min(l + blocksz - 1, q - 1);
vis.assign(m, 0);
if (l >= q) break;
for (int i = 0; i < n; i++) min_v[i].clear(), max_v[i].clear(), qus_v[i].clear();
for (int i = l; i <= r; i++) {
vis[refer[qu[i].plan_day]] = 1;
qus_v[qu[i].collapse_town].pb(i);
}
for (int i = 0; i < m; i++) {
if (state[i] && !vis[i]) {
min_v[edges[i].fi].pb(i);
max_v[edges[i].se].pb(i);
}
}
make_set(n);
for (int i = 0; i <= n - 2; i++) {
for (int id : max_v[i])
add(edges[id].fi, edges[id].se);
for (int id : qus_v[i]) {
int cnt_op = 0;
for (int j = prv + 1; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
for (int j = qu[l].plan_day; j <= qu[r].plan_day; j++) {
if (state[refer[j]] && edges[refer[j]].se <= i)
cnt_op += add(edges[refer[j]].fi, edges[refer[j]].se);
}
for (int j = prv + 1; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
ans[qu[id].id] += sz_comp - (n - i - 1);
// cout << "left " << qu[id].id << " " << sz_comp - (n - i - 1) << endl;
while (cnt_op--) go_back();
}
}
make_set(n);
for (int i = n - 1; i >= 1; i--) {
for (int id : min_v[i])
add(edges[id].fi, edges[id].se);
for (int id : qus_v[i - 1]) {
int cnt_op = 0;
for (int j = prv + 1; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
for (int j = qu[l].plan_day; j <= qu[r].plan_day; j++) {
if (state[refer[j]] && i <= edges[refer[j]].fi)
cnt_op += add(edges[refer[j]].fi, edges[refer[j]].se);
}
for (int j = prv + 1; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
ans[qu[id].id] += sz_comp - i;
// cout << "rt " << qu[id].id << " " << sz_comp - i << endl;
while (cnt_op--) go_back();
}
}
for (int j = prv + 1; j <= qu[r].plan_day; j++) state[refer[j]] ^= 1;
prv = qu[r].plan_day;
curblock++;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
620 KB |
Output is correct |
| 2 |
Correct |
4 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
| 4 |
Correct |
3 ms |
636 KB |
Output is correct |
| 5 |
Incorrect |
38 ms |
620 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
3556 KB |
Output is correct |
| 2 |
Correct |
41 ms |
3556 KB |
Output is correct |
| 3 |
Correct |
641 ms |
7648 KB |
Output is correct |
| 4 |
Correct |
44 ms |
4072 KB |
Output is correct |
| 5 |
Correct |
542 ms |
8416 KB |
Output is correct |
| 6 |
Correct |
100 ms |
4928 KB |
Output is correct |
| 7 |
Correct |
1370 ms |
17632 KB |
Output is correct |
| 8 |
Correct |
671 ms |
13664 KB |
Output is correct |
| 9 |
Correct |
485 ms |
12256 KB |
Output is correct |
| 10 |
Correct |
487 ms |
12256 KB |
Output is correct |
| 11 |
Correct |
557 ms |
12768 KB |
Output is correct |
| 12 |
Correct |
1193 ms |
21216 KB |
Output is correct |
| 13 |
Correct |
2828 ms |
25244 KB |
Output is correct |
| 14 |
Correct |
6709 ms |
29476 KB |
Output is correct |
| 15 |
Correct |
4617 ms |
29280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
3556 KB |
Output is correct |
| 2 |
Correct |
52 ms |
3556 KB |
Output is correct |
| 3 |
Correct |
43 ms |
4072 KB |
Output is correct |
| 4 |
Correct |
43 ms |
4072 KB |
Output is correct |
| 5 |
Correct |
55 ms |
4220 KB |
Output is correct |
| 6 |
Correct |
119 ms |
4832 KB |
Output is correct |
| 7 |
Incorrect |
1088 ms |
14432 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
620 KB |
Output is correct |
| 2 |
Correct |
4 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
| 4 |
Correct |
3 ms |
636 KB |
Output is correct |
| 5 |
Incorrect |
38 ms |
620 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
