#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> brute(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) {
int m = (int)t.size();
int q = (int)w.size();
for (int i = 0; i < m; i++) {
if (x[i] > y[i]) {
swap(x[i], y[i]);
assert(0 <= x[i] && x[i] < y[i] && y[i] < n);
}
}
assert((int) t.size() == m);
assert((int) x.size() == m);
assert((int) y.size() == m);
assert((int) w.size() == q);
assert((int) p.size() == q);
vector<int> sol((int) w.size());
for (int iq = 0; iq < (int) w.size(); iq++) {
set<pair<int, int>> s;
for (int i = 0; i <= w[iq]; i++) {
pair<int, int> cur = make_pair(x[i], y[i]);
if (s.count(cur)) {
s.erase(cur);
} else {
s.insert(cur);
}
}
vector<pair<int, int>> ve;
for (auto &it : s) {
if (it.first <= p[iq] && it.second > p[iq]) {
continue;
}
ve.push_back(it);
}
vector<int> t(n);
iota(t.begin(), t.end(), 0);
int comps = n;
function<int(int)> getpap = [&] (int a) {
if (t[a] == a) {
return a;
} else {
return t[a] = getpap(t[a]);
}
};
function<void(int, int)> unite = [&] (int a, int b) {
a = getpap(a);
b = getpap(b);
if (a != b) {
comps--;
t[a] = b;
}
};
for (auto &it : ve) {
unite(it.first, it.second);
}
sol[iq] = comps;
}
return sol;
}
const int NN = 100000 + 7;
int dsu[2][NN], un[2], lt[2][NN], tt[2];
void initial(int id) {
assert(0 <= id && id < 2);
un[id] = 0;
for (int i = 0; i < NN; i++) {
dsu[id][i] = i;
}
}
int root(int id, int a) {
if (lt[id][a] != tt[id]) {
dsu[id][a] = a;
lt[id][a] = tt[id];
}
if (a == dsu[id][a]) {
return a;
} else {
return dsu[id][a] = root(id, dsu[id][a]);
}
}
void unite(int id, int a, int b) {
// if (id == 1) {
// }
a = root(id, a);
b = root(id, b);
if (id) {
lt[id][a] = tt[id];
lt[id][b] = tt[id];
}
if (a != b) {
un[id]++;
dsu[id][a] = b;
}
}
const int edgeM = 400;
vector<int> smart(int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> w, vector<int> p) {
initial(0);
initial(1);
struct Edge {
int type;
int x;
int y;
int id;
};
vector<Edge> edges;
int m = (int)T.size();
int q = (int)w.size();
bool ok = (n <= 5000 && q <= 5000 && m <= 5000);
vector<pair<int, int>> theEdge;
vector<int> active;
{
map<pair<int, int>, int> inds;
int kek = 0;
for (int i = 0; i < m; i++) {
if (X[i] > Y[i]) {
swap(X[i], Y[i]);
}
if (!inds.count({X[i], Y[i]})) {
inds[{X[i], Y[i]}] = kek++;
theEdge.push_back({X[i], Y[i]});
active.push_back(0);
}
edges.push_back({T[i], X[i], Y[i], inds[{X[i], Y[i]}]});
}
}
function<bool(int, int)> cmp = [&] (int i, int j) {
return p[i] < p[j];
};
function<bool(int, int)> cmpE = [&] (int i, int j) {
return theEdge[i].second < theEdge[j].second;
};
assert((int) T.size() == m);
assert((int) X.size() == m);
assert((int) Y.size() == m);
assert((int) w.size() == q);
assert((int) p.size() == q);
vector<int> sol((int) w.size());
for (int ISTEP = 1; ISTEP <= 2; ISTEP++) {
for (auto &x : active) {
x = 0;
}
vector<int> edgeBucket(m), edgeFirst(m), edgeLast(m);
vector<int> O;
for (int i = 0; i < m; i++) {
edgeBucket[i] = i / edgeM;
edgeLast[edgeBucket[i]] = i;
}
for (int i = m - 1; i >= 0; i--) {
edgeFirst[edgeBucket[i]] = i;
}
vector<vector<int>> inds(m);
for (int i = 0; i < q; i++) {
inds[w[i]].push_back(i);
}
vector<int> order((int) active.size());
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), cmpE);
for (int edgeBucketId = edgeBucket[0]; edgeBucketId <= edgeBucket[m - 1]; edgeBucketId++) {
// cout << ISTEP << ", " << edgeBucketId << " out of " << edgeBucket[m - 1] << "\n";
tt[0]++;
tt[1]++;
un[0] = un[1] = 0;
vector<bool> use_now((int) active.size(), 0);
vector<int> current = active;
vector<int> guys;
for (int step = edgeFirst[edgeBucketId]; step <= edgeLast[edgeBucketId]; step++) {
use_now[edges[step].id] = 1;
for (auto &iq : inds[step]) {
guys.push_back(iq);
}
}
vector<pair<int, int>> additional;
vector<int> here;
for (auto &i : order) {
if (use_now[i]) {
here.push_back(i);
}
if (active[i] && !use_now[i]) {
additional.push_back(theEdge[i]);
}
}
int ptr = 0;
sort(guys.begin(), guys.end(), cmp);
for (auto &iq : guys) {
tt[1]++;
un[1] = 0;
for (int step = edgeFirst[edgeBucketId]; step <= w[iq]; step++) {
current[edges[step].id] ^= 1;
}
vector<pair<int, int>> specific;
for (auto &i : here) {
if (current[i]) {
specific.push_back(theEdge[i]);
}
}
for (int step = edgeFirst[edgeBucketId]; step <= w[iq]; step++) {
current[edges[step].id] = active[edges[step].id];
}
while (ptr < (int) additional.size() && additional[ptr].second <= p[iq]) {
unite(0, additional[ptr].first, additional[ptr].second);
ptr++;
}
// assert((int) specific.size() <= edgeM);
//if (!ok) continue;
for (auto &it : specific) {
if (it.second <= p[iq]) {
unite(1, root(0, it.first), root(0, it.second));
}
}
sol[iq] += p[iq] + 1 - (un[0] + un[1]);
}
for (int step = edgeFirst[edgeBucketId]; step <= edgeLast[edgeBucketId]; step++) {
active[edges[step].id] ^= 1;
}
}
for (int i = 0; i < m; i++) {
swap(edges[i].x, edges[i].y);
edges[i].x = n - 1 - edges[i].x;
edges[i].y = n - 1 - edges[i].y;
}
for (int i = 0; i < q; i++) {
p[i] = n - 2 - p[i];
}
for (auto &it : theEdge) {
swap(it.first, it.second);
it.first = n - 1 - it.first;
it.second = n - 1 - it.second;
}
}
return sol;
}
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
auto x = smart(N,T,X,Y,W,P); return x;
auto y = brute(N,T,X,Y,W,P);
int dif = 0, good = 0;
for (int i = 0; i < (int) x.size(); i++) {
dif += (x[i] != y[i]);
good += (x[i] == y[i]);
}
cout << good << ", " << dif << "\n";
assert(x==y);
exit(0);
return smart(N,T,X,Y,W,P);
}
Compilation message
collapse.cpp: In function 'std::vector<int> smart(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:126:8: warning: unused variable 'ok' [-Wunused-variable]
126 | bool ok = (n <= 5000 && q <= 5000 && m <= 5000);
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
1740 KB |
Output is correct |
2 |
Correct |
3 ms |
1228 KB |
Output is correct |
3 |
Correct |
10 ms |
1324 KB |
Output is correct |
4 |
Correct |
10 ms |
1228 KB |
Output is correct |
5 |
Correct |
24 ms |
1740 KB |
Output is correct |
6 |
Correct |
67 ms |
1996 KB |
Output is correct |
7 |
Correct |
3 ms |
1356 KB |
Output is correct |
8 |
Correct |
5 ms |
1356 KB |
Output is correct |
9 |
Correct |
25 ms |
1868 KB |
Output is correct |
10 |
Correct |
50 ms |
1860 KB |
Output is correct |
11 |
Correct |
64 ms |
2052 KB |
Output is correct |
12 |
Correct |
61 ms |
2024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
5112 KB |
Output is correct |
2 |
Correct |
54 ms |
5288 KB |
Output is correct |
3 |
Correct |
416 ms |
15588 KB |
Output is correct |
4 |
Correct |
138 ms |
5556 KB |
Output is correct |
5 |
Correct |
707 ms |
17340 KB |
Output is correct |
6 |
Correct |
763 ms |
6108 KB |
Output is correct |
7 |
Correct |
1459 ms |
21304 KB |
Output is correct |
8 |
Correct |
728 ms |
18896 KB |
Output is correct |
9 |
Correct |
51 ms |
5820 KB |
Output is correct |
10 |
Correct |
88 ms |
5988 KB |
Output is correct |
11 |
Correct |
596 ms |
6684 KB |
Output is correct |
12 |
Correct |
728 ms |
19748 KB |
Output is correct |
13 |
Correct |
1362 ms |
21080 KB |
Output is correct |
14 |
Correct |
1525 ms |
22500 KB |
Output is correct |
15 |
Correct |
1450 ms |
22528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
5048 KB |
Output is correct |
2 |
Correct |
78 ms |
5224 KB |
Output is correct |
3 |
Correct |
114 ms |
5364 KB |
Output is correct |
4 |
Correct |
167 ms |
5564 KB |
Output is correct |
5 |
Correct |
963 ms |
5232 KB |
Output is correct |
6 |
Correct |
953 ms |
5384 KB |
Output is correct |
7 |
Correct |
1653 ms |
17084 KB |
Output is correct |
8 |
Correct |
2777 ms |
20608 KB |
Output is correct |
9 |
Correct |
66 ms |
5936 KB |
Output is correct |
10 |
Correct |
786 ms |
6780 KB |
Output is correct |
11 |
Correct |
2345 ms |
22068 KB |
Output is correct |
12 |
Correct |
2741 ms |
21668 KB |
Output is correct |
13 |
Correct |
2695 ms |
22400 KB |
Output is correct |
14 |
Correct |
2713 ms |
21624 KB |
Output is correct |
15 |
Correct |
2466 ms |
22364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
1740 KB |
Output is correct |
2 |
Correct |
3 ms |
1228 KB |
Output is correct |
3 |
Correct |
10 ms |
1324 KB |
Output is correct |
4 |
Correct |
10 ms |
1228 KB |
Output is correct |
5 |
Correct |
24 ms |
1740 KB |
Output is correct |
6 |
Correct |
67 ms |
1996 KB |
Output is correct |
7 |
Correct |
3 ms |
1356 KB |
Output is correct |
8 |
Correct |
5 ms |
1356 KB |
Output is correct |
9 |
Correct |
25 ms |
1868 KB |
Output is correct |
10 |
Correct |
50 ms |
1860 KB |
Output is correct |
11 |
Correct |
64 ms |
2052 KB |
Output is correct |
12 |
Correct |
61 ms |
2024 KB |
Output is correct |
13 |
Correct |
51 ms |
5112 KB |
Output is correct |
14 |
Correct |
54 ms |
5288 KB |
Output is correct |
15 |
Correct |
416 ms |
15588 KB |
Output is correct |
16 |
Correct |
138 ms |
5556 KB |
Output is correct |
17 |
Correct |
707 ms |
17340 KB |
Output is correct |
18 |
Correct |
763 ms |
6108 KB |
Output is correct |
19 |
Correct |
1459 ms |
21304 KB |
Output is correct |
20 |
Correct |
728 ms |
18896 KB |
Output is correct |
21 |
Correct |
51 ms |
5820 KB |
Output is correct |
22 |
Correct |
88 ms |
5988 KB |
Output is correct |
23 |
Correct |
596 ms |
6684 KB |
Output is correct |
24 |
Correct |
728 ms |
19748 KB |
Output is correct |
25 |
Correct |
1362 ms |
21080 KB |
Output is correct |
26 |
Correct |
1525 ms |
22500 KB |
Output is correct |
27 |
Correct |
1450 ms |
22528 KB |
Output is correct |
28 |
Correct |
44 ms |
5048 KB |
Output is correct |
29 |
Correct |
78 ms |
5224 KB |
Output is correct |
30 |
Correct |
114 ms |
5364 KB |
Output is correct |
31 |
Correct |
167 ms |
5564 KB |
Output is correct |
32 |
Correct |
963 ms |
5232 KB |
Output is correct |
33 |
Correct |
953 ms |
5384 KB |
Output is correct |
34 |
Correct |
1653 ms |
17084 KB |
Output is correct |
35 |
Correct |
2777 ms |
20608 KB |
Output is correct |
36 |
Correct |
66 ms |
5936 KB |
Output is correct |
37 |
Correct |
786 ms |
6780 KB |
Output is correct |
38 |
Correct |
2345 ms |
22068 KB |
Output is correct |
39 |
Correct |
2741 ms |
21668 KB |
Output is correct |
40 |
Correct |
2695 ms |
22400 KB |
Output is correct |
41 |
Correct |
2713 ms |
21624 KB |
Output is correct |
42 |
Correct |
2466 ms |
22364 KB |
Output is correct |
43 |
Correct |
687 ms |
17388 KB |
Output is correct |
44 |
Correct |
2153 ms |
20252 KB |
Output is correct |
45 |
Correct |
762 ms |
17876 KB |
Output is correct |
46 |
Correct |
2706 ms |
21096 KB |
Output is correct |
47 |
Correct |
63 ms |
5892 KB |
Output is correct |
48 |
Correct |
95 ms |
6104 KB |
Output is correct |
49 |
Correct |
724 ms |
6760 KB |
Output is correct |
50 |
Correct |
893 ms |
8228 KB |
Output is correct |
51 |
Correct |
928 ms |
18780 KB |
Output is correct |
52 |
Correct |
1271 ms |
19428 KB |
Output is correct |
53 |
Correct |
1397 ms |
19232 KB |
Output is correct |
54 |
Correct |
1614 ms |
20328 KB |
Output is correct |
55 |
Correct |
1627 ms |
20268 KB |
Output is correct |
56 |
Correct |
2025 ms |
20600 KB |
Output is correct |
57 |
Correct |
2451 ms |
21512 KB |
Output is correct |
58 |
Correct |
2546 ms |
21528 KB |
Output is correct |
59 |
Correct |
2519 ms |
22132 KB |
Output is correct |
60 |
Correct |
3075 ms |
21624 KB |
Output is correct |