#include "collapse.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
constexpr int B = 5050;
struct DSU{
int path[100100], sz[100100], cnt;
vector<pair<int, int>> mylog;
void init(int n){for (int i=1;i<=n;i++){path[i] = i; sz[i] = 1;} mylog.clear(); cnt = 0;}
int find(int s){
if (s==path[s]) return s;
return find(path[s]);
}
bool merge(int x, int y){
//printf("merge: %d %d\n", x, y);
x = find(x), y = find(y);
if (x==y) return 0;
cnt++;
if (sz[x] > sz[y]) swap(x, y);
path[x] = y;
sz[y] += sz[x];
mylog.emplace_back(x, sz[x]);
return 1;
}
void rollback(int c){
while(c--){
auto [x, _sz] = mylog.back(); mylog.pop_back();
sz[path[x]] -= _sz;
path[x] = x;
--cnt;
}
}
int count(int x){return x - cnt;}
}dsu;
struct Edge{
int x, y;
Edge(){}
Edge(int _x, int _y): x(_x), y(_y) {}
}E[100100];
struct Query{
int w, p, i;
Query(){}
Query(int _w, int _p, int _i): w(_w), p(_p), i(_i) {}
};
vector<Query> bucket[100100];
map<int, int> mp[100100];
int idx[100100], updated[100100], on[100100], ans[100100];
bool cmpB(const Query &x, const Query &y){return x.p < y.p;}
bool cmpE(int x, int y){return E[x].y < E[y].y;}
void calc(int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P){
int c = T.size(), q = W.size();
///init
for (int i=1;i<=c;i++){
mp[i].clear();
on[i] = 0;
updated[i] = 0;
}
for (int i=0;i<=c/B;i++) bucket[i].clear();
fill(E, E+c+1, Edge(0, 0));
///
int Ecnt = 0;
for (int i=1;i<=c;i++){
int op, x, y;
op = T[i-1], x = X[i-1], y = Y[i-1];
if (x==y) {idx[i] = 0; continue;}
if (x > y) swap(x, y);
if (mp[x].find(y)==mp[x].end()){
mp[x][y] = ++Ecnt;
E[Ecnt] = Edge(x, y);
}
idx[i] = mp[x][y];
}
for (int i=1;i<=q;i++){
int w, p;
w = W[i-1], p = P[i-1];
bucket[w/B].emplace_back(w, p, i);
}
vector<int> onE;
for (int z=0;z<=c/B;z++){
int l = z*B, r = (z+1)*B;
for (int i=l;i<r;i++) if (idx[i]) updated[idx[i]] = 1;
sort(bucket[z].begin(), bucket[z].end(), cmpB);
dsu.init(n);
int pt = 0;
for (auto &[w, p, qi]:bucket[z]){
while(pt < (int)onE.size() && E[onE[pt]].y <= p){
if (!updated[onE[pt]]) dsu.merge(E[onE[pt]].x, E[onE[pt]].y);
pt++;
}
for (int i=l;i<=w;i++) if (idx[i]) on[idx[i]] ^= 1;
int cnt = 0;
for (int i=l;i<r;i++) if (idx[i] && on[idx[i]] && E[idx[i]].y <= p){
if (dsu.merge(E[idx[i]].x, E[idx[i]].y)) cnt++;
}
//printf("ok %d -> %d\n", qi, dsu.count(p));
ans[qi] += dsu.count(p);
dsu.rollback(cnt);
for (int i=l;i<=w;i++) if (idx[i]) on[idx[i]] ^= 1;
}
for (int i=l;i<r;i++) if (idx[i]) on[idx[i]] ^= 1, updated[idx[i]] = 0;
vector<int> nE;
for (auto &x:onE) if (on[x]) nE.push_back(x);
for (int i=l;i<r;i++) if (on[idx[i]]) nE.push_back(idx[i]);
sort(nE.begin(), nE.end(), cmpE);
nE.erase(unique(nE.begin(), nE.end()), nE.end());
swap(nE, onE);
}
}
std::vector<int> simulateCollapse(
int N,
std::vector<int> T,
std::vector<int> X,
std::vector<int> Y,
std::vector<int> W,
std::vector<int> P
) {
for (auto &x:X) ++x;
for (auto &x:Y) ++x;
for (auto &x:W) ++x;
for (auto &x:P) ++x;
calc(N, T, X, Y, W, P);
for (auto &x:X) x = N+1 - x;
for (auto &y:Y) y = N+1 - y;
for (auto &p:P) p = N - p;
calc(N, T, X, Y, W, P);
vector<int> ret(W.size());
for (int i=0;i<(int)W.size();i++) ret[i] = ans[i+1];
return ret;
}
Compilation message
collapse.cpp: In function 'void calc(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:72:13: warning: variable 'op' set but not used [-Wunused-but-set-variable]
72 | int op, x, y;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
8012 KB |
Output is correct |
| 2 |
Correct |
40 ms |
7676 KB |
Output is correct |
| 3 |
Correct |
42 ms |
7688 KB |
Output is correct |
| 4 |
Correct |
43 ms |
7700 KB |
Output is correct |
| 5 |
Correct |
375 ms |
8016 KB |
Output is correct |
| 6 |
Correct |
303 ms |
8148 KB |
Output is correct |
| 7 |
Correct |
39 ms |
7756 KB |
Output is correct |
| 8 |
Correct |
40 ms |
7732 KB |
Output is correct |
| 9 |
Correct |
182 ms |
8208 KB |
Output is correct |
| 10 |
Correct |
307 ms |
8232 KB |
Output is correct |
| 11 |
Correct |
346 ms |
8316 KB |
Output is correct |
| 12 |
Correct |
342 ms |
8316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
729 ms |
11828 KB |
Output is correct |
| 2 |
Correct |
703 ms |
11728 KB |
Output is correct |
| 3 |
Runtime error |
4056 ms |
36312 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
701 ms |
11804 KB |
Output is correct |
| 2 |
Correct |
701 ms |
11844 KB |
Output is correct |
| 3 |
Correct |
727 ms |
11880 KB |
Output is correct |
| 4 |
Correct |
743 ms |
11908 KB |
Output is correct |
| 5 |
Correct |
1152 ms |
12140 KB |
Output is correct |
| 6 |
Correct |
5785 ms |
12724 KB |
Output is correct |
| 7 |
Correct |
5080 ms |
22308 KB |
Output is correct |
| 8 |
Runtime error |
2904 ms |
49488 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
8012 KB |
Output is correct |
| 2 |
Correct |
40 ms |
7676 KB |
Output is correct |
| 3 |
Correct |
42 ms |
7688 KB |
Output is correct |
| 4 |
Correct |
43 ms |
7700 KB |
Output is correct |
| 5 |
Correct |
375 ms |
8016 KB |
Output is correct |
| 6 |
Correct |
303 ms |
8148 KB |
Output is correct |
| 7 |
Correct |
39 ms |
7756 KB |
Output is correct |
| 8 |
Correct |
40 ms |
7732 KB |
Output is correct |
| 9 |
Correct |
182 ms |
8208 KB |
Output is correct |
| 10 |
Correct |
307 ms |
8232 KB |
Output is correct |
| 11 |
Correct |
346 ms |
8316 KB |
Output is correct |
| 12 |
Correct |
342 ms |
8316 KB |
Output is correct |
| 13 |
Correct |
729 ms |
11828 KB |
Output is correct |
| 14 |
Correct |
703 ms |
11728 KB |
Output is correct |
| 15 |
Runtime error |
4056 ms |
36312 KB |
Execution killed with signal 11 |
| 16 |
Halted |
0 ms |
0 KB |
- |
