#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
int edges[MAXN][2];
map<pair<int, int>, int> mp;
vector<int> t, x, y, w, p;
vector<int> seg[MAXN*4];
int ans[MAXN];
int n, m, q;
class dsu {
private:
vector<pair<int, int> > st[MAXN];
int rep[MAXN];
int repp[MAXN];
public:
int cnt;
void init() {
for(int i = 0; i <= n; i++) rep[i] = i, repp[i] = 1;
cnt = n;
}
int find(int x) {
return rep[x] == x ? x : find(rep[x]);
}
void une(int a, int b) {
int aa = find(a);
int bb = find(b);
st[a].push_back({aa, repp[aa]});
st[b].push_back({bb, repp[bb]});
a = aa, b = bb;
if(a == b) return;
cnt--;
if(repp[a] > repp[b]) swap(a, b);
rep[a] = b;
if(repp[a] == repp[b]) repp[b]++;
}
void undo(int a, int b) {
// printf("undo %d %d\n", a, b);
auto aa = st[a].back(); st[a].pop_back();
auto bb = st[b].back(); st[b].pop_back();
a = aa.first; b = bb.first;
if(a == b) return;
cnt++;
rep[a] = aa.first; repp[a] = aa.second;
rep[b] = bb.first; repp[b] = bb.second;
}
};
dsu graph;
void update(int sind, int l, int r, int ql, int qr, int val) {
if(ql > r || qr < l) return;
if(ql <= l && qr >= r) {
seg[sind].push_back(val);
return;
}
int m = (l+r)/2;
int e = sind*2; int d = e+1;
update(e, l, m, ql, qr, val);
update(d, m+1, r, ql, qr, val);
}
void prepare() {
for(int i = 0; i < m; i++) {
int a = x[i], b = y[i];
if(a > b) swap(a, b);
if(a <= p[0] && b > p[0]) continue;
if(!t[i]) {
mp[{a, b}] = i;
edges[i][0] = i+1;
}
else {
int id = mp[{a, b}];
edges[id][1] = i+1;
}
}
for(int i = 0; i < m; i++) {
if(!edges[i][0]) continue;
if(!edges[i][1]) edges[i][1] = m+1;
update(1, 1, m+1, edges[i][0], edges[i][1], i);
}
graph.init();
}
void solve(int sind, int l, int r) {
// printf("-- %d\n", sind);
for(int id : seg[sind]) graph.une(x[id], y[id]);
if(l != r) {
int m = (l+r)/2;
int e = sind*2; int d = e+1;
solve(e, l, m);
solve(d, m+1, r);
}
else {
// printf("get cnt\n");
ans[l] = graph.cnt;
}
for(int i = seg[sind].size()-1; i >= 0; i--) {
int id = seg[sind][i];
graph.undo(x[id], y[id]);
}
}
vector<int> simulateCollapse(
int N,
vector<int> T,
vector<int> X,
vector<int> Y,
vector<int> W,
vector<int> P
) {
n = N;
m = T.size();
q = W.size();
t = T;
x = X;
y = Y;
w = W;
p = P;
prepare();
solve(1, 1, m+1);
// for(int i = 1; i <= m+1; i++) printf("%d ", ans[i]);
vector<int> fans;
for(int day : W) fans.push_back(ans[day+1]);
return fans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12536 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
12280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
15476 KB |
Output is correct |
| 2 |
Incorrect |
40 ms |
15476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
15476 KB |
Output is correct |
| 2 |
Incorrect |
39 ms |
15452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12536 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
12280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
