#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
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 = 333;
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) {
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:63:8: warning: unused variable 'ok' [-Wunused-variable]
63 | bool ok = (n <= 5000 && q <= 5000 && m <= 5000);
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
1740 KB |
Output is correct |
2 |
Correct |
4 ms |
1228 KB |
Output is correct |
3 |
Correct |
7 ms |
1324 KB |
Output is correct |
4 |
Correct |
9 ms |
1228 KB |
Output is correct |
5 |
Correct |
18 ms |
1776 KB |
Output is correct |
6 |
Correct |
50 ms |
2000 KB |
Output is correct |
7 |
Correct |
4 ms |
1356 KB |
Output is correct |
8 |
Correct |
5 ms |
1356 KB |
Output is correct |
9 |
Correct |
24 ms |
1872 KB |
Output is correct |
10 |
Correct |
48 ms |
1876 KB |
Output is correct |
11 |
Correct |
58 ms |
2032 KB |
Output is correct |
12 |
Correct |
60 ms |
2032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
5120 KB |
Output is correct |
2 |
Correct |
61 ms |
5324 KB |
Output is correct |
3 |
Correct |
397 ms |
15556 KB |
Output is correct |
4 |
Correct |
167 ms |
5728 KB |
Output is correct |
5 |
Correct |
648 ms |
15964 KB |
Output is correct |
6 |
Correct |
699 ms |
5512 KB |
Output is correct |
7 |
Correct |
1574 ms |
19752 KB |
Output is correct |
8 |
Correct |
699 ms |
16932 KB |
Output is correct |
9 |
Correct |
47 ms |
5296 KB |
Output is correct |
10 |
Correct |
99 ms |
5452 KB |
Output is correct |
11 |
Correct |
590 ms |
5836 KB |
Output is correct |
12 |
Correct |
716 ms |
17488 KB |
Output is correct |
13 |
Correct |
1287 ms |
18688 KB |
Output is correct |
14 |
Correct |
1495 ms |
20096 KB |
Output is correct |
15 |
Correct |
1431 ms |
20288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
5132 KB |
Output is correct |
2 |
Correct |
80 ms |
5220 KB |
Output is correct |
3 |
Correct |
102 ms |
5368 KB |
Output is correct |
4 |
Correct |
165 ms |
5568 KB |
Output is correct |
5 |
Correct |
765 ms |
5236 KB |
Output is correct |
6 |
Correct |
857 ms |
5344 KB |
Output is correct |
7 |
Correct |
1612 ms |
15704 KB |
Output is correct |
8 |
Correct |
2908 ms |
18968 KB |
Output is correct |
9 |
Correct |
69 ms |
5404 KB |
Output is correct |
10 |
Correct |
763 ms |
5964 KB |
Output is correct |
11 |
Correct |
2598 ms |
19780 KB |
Output is correct |
12 |
Correct |
2932 ms |
19380 KB |
Output is correct |
13 |
Correct |
2658 ms |
20384 KB |
Output is correct |
14 |
Correct |
2775 ms |
19500 KB |
Output is correct |
15 |
Correct |
2477 ms |
20252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
1740 KB |
Output is correct |
2 |
Correct |
4 ms |
1228 KB |
Output is correct |
3 |
Correct |
7 ms |
1324 KB |
Output is correct |
4 |
Correct |
9 ms |
1228 KB |
Output is correct |
5 |
Correct |
18 ms |
1776 KB |
Output is correct |
6 |
Correct |
50 ms |
2000 KB |
Output is correct |
7 |
Correct |
4 ms |
1356 KB |
Output is correct |
8 |
Correct |
5 ms |
1356 KB |
Output is correct |
9 |
Correct |
24 ms |
1872 KB |
Output is correct |
10 |
Correct |
48 ms |
1876 KB |
Output is correct |
11 |
Correct |
58 ms |
2032 KB |
Output is correct |
12 |
Correct |
60 ms |
2032 KB |
Output is correct |
13 |
Correct |
62 ms |
5120 KB |
Output is correct |
14 |
Correct |
61 ms |
5324 KB |
Output is correct |
15 |
Correct |
397 ms |
15556 KB |
Output is correct |
16 |
Correct |
167 ms |
5728 KB |
Output is correct |
17 |
Correct |
648 ms |
15964 KB |
Output is correct |
18 |
Correct |
699 ms |
5512 KB |
Output is correct |
19 |
Correct |
1574 ms |
19752 KB |
Output is correct |
20 |
Correct |
699 ms |
16932 KB |
Output is correct |
21 |
Correct |
47 ms |
5296 KB |
Output is correct |
22 |
Correct |
99 ms |
5452 KB |
Output is correct |
23 |
Correct |
590 ms |
5836 KB |
Output is correct |
24 |
Correct |
716 ms |
17488 KB |
Output is correct |
25 |
Correct |
1287 ms |
18688 KB |
Output is correct |
26 |
Correct |
1495 ms |
20096 KB |
Output is correct |
27 |
Correct |
1431 ms |
20288 KB |
Output is correct |
28 |
Correct |
43 ms |
5132 KB |
Output is correct |
29 |
Correct |
80 ms |
5220 KB |
Output is correct |
30 |
Correct |
102 ms |
5368 KB |
Output is correct |
31 |
Correct |
165 ms |
5568 KB |
Output is correct |
32 |
Correct |
765 ms |
5236 KB |
Output is correct |
33 |
Correct |
857 ms |
5344 KB |
Output is correct |
34 |
Correct |
1612 ms |
15704 KB |
Output is correct |
35 |
Correct |
2908 ms |
18968 KB |
Output is correct |
36 |
Correct |
69 ms |
5404 KB |
Output is correct |
37 |
Correct |
763 ms |
5964 KB |
Output is correct |
38 |
Correct |
2598 ms |
19780 KB |
Output is correct |
39 |
Correct |
2932 ms |
19380 KB |
Output is correct |
40 |
Correct |
2658 ms |
20384 KB |
Output is correct |
41 |
Correct |
2775 ms |
19500 KB |
Output is correct |
42 |
Correct |
2477 ms |
20252 KB |
Output is correct |
43 |
Correct |
618 ms |
15668 KB |
Output is correct |
44 |
Correct |
2136 ms |
18812 KB |
Output is correct |
45 |
Correct |
729 ms |
15924 KB |
Output is correct |
46 |
Correct |
2782 ms |
19316 KB |
Output is correct |
47 |
Correct |
67 ms |
5400 KB |
Output is correct |
48 |
Correct |
99 ms |
5544 KB |
Output is correct |
49 |
Correct |
662 ms |
6212 KB |
Output is correct |
50 |
Correct |
801 ms |
7348 KB |
Output is correct |
51 |
Correct |
852 ms |
16436 KB |
Output is correct |
52 |
Correct |
1174 ms |
17248 KB |
Output is correct |
53 |
Correct |
1241 ms |
17024 KB |
Output is correct |
54 |
Correct |
1507 ms |
18128 KB |
Output is correct |
55 |
Correct |
1558 ms |
17916 KB |
Output is correct |
56 |
Correct |
1894 ms |
18228 KB |
Output is correct |
57 |
Correct |
2255 ms |
19124 KB |
Output is correct |
58 |
Correct |
2276 ms |
19204 KB |
Output is correct |
59 |
Correct |
2363 ms |
19688 KB |
Output is correct |
60 |
Correct |
2776 ms |
19112 KB |
Output is correct |