#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
const int NN = 100000 + 7;
int dsu[2][NN], un[2];
vector<int> modif[2];
void clr(int id) {
modif[id].clear();
assert(0 <= id && id < 2);
un[id] = 0;
for (int i = 0; i < NN; i++) {
dsu[id][i] = i;
}
}
void restore(int id) {
un[id] = 0;
for (auto &i : modif[id]) {
dsu[id][i] = i;
}
}
int root(int id, int a) {
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) {
modif[id].push_back(a);
modif[id].push_back(b);
a = root(id, a);
b = root(id, b);
modif[id].push_back(a);
modif[id].push_back(b);
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) {
bool ok = (n > 5000);
clr(0);
clr(1);
struct Edge {
int type;
int x;
int y;
int id;
};
vector<Edge> edges;
int m = (int)T.size();
int q = (int)w.size();
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);
if (ok) continue;
for (int edgeBucketId = edgeBucket[0]; edgeBucketId <= edgeBucket[m - 1]; edgeBucketId++) {
clr(0);
clr(1);
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) {
restore(1);
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++;
}
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);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
1740 KB |
Output is correct |
| 2 |
Correct |
67 ms |
1388 KB |
Output is correct |
| 3 |
Correct |
291 ms |
1608 KB |
Output is correct |
| 4 |
Correct |
897 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
54 ms |
1844 KB |
Output is correct |
| 6 |
Correct |
503 ms |
2484 KB |
Output is correct |
| 7 |
Correct |
101 ms |
1432 KB |
Output is correct |
| 8 |
Correct |
239 ms |
1616 KB |
Output is correct |
| 9 |
Correct |
79 ms |
1996 KB |
Output is correct |
| 10 |
Correct |
428 ms |
2432 KB |
Output is correct |
| 11 |
Correct |
533 ms |
2504 KB |
Output is correct |
| 12 |
Correct |
519 ms |
2608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
5048 KB |
Output is correct |
| 2 |
Execution timed out |
15035 ms |
6260 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
5104 KB |
Output is correct |
| 2 |
Execution timed out |
15065 ms |
6992 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
1740 KB |
Output is correct |
| 2 |
Correct |
67 ms |
1388 KB |
Output is correct |
| 3 |
Correct |
291 ms |
1608 KB |
Output is correct |
| 4 |
Correct |
897 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
54 ms |
1844 KB |
Output is correct |
| 6 |
Correct |
503 ms |
2484 KB |
Output is correct |
| 7 |
Correct |
101 ms |
1432 KB |
Output is correct |
| 8 |
Correct |
239 ms |
1616 KB |
Output is correct |
| 9 |
Correct |
79 ms |
1996 KB |
Output is correct |
| 10 |
Correct |
428 ms |
2432 KB |
Output is correct |
| 11 |
Correct |
533 ms |
2504 KB |
Output is correct |
| 12 |
Correct |
519 ms |
2608 KB |
Output is correct |
| 13 |
Correct |
42 ms |
5048 KB |
Output is correct |
| 14 |
Execution timed out |
15035 ms |
6260 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
