//S3
#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;
const int sq = 500;
class dsu_type{
public:
int n, com;
int head[maxn], sz[maxn];
stack<pii> stk;
int findhead(int x) {
if(x==head[x]) return x;
return findhead(head[x]);
}
void init(int _n) {
n = com = _n;
for(int i=0;i<n;++i) {
head[i] = i;
sz[i] = 1;
}
while(!stk.empty()) stk.pop();
}
void add_edge(int u, int v) {
int x = findhead(u), y = findhead(v);
if(sz[x] > sz[y]) swap(x,y);
stk.push({x,y});
if(x!=y) {
head[x] = y;
sz[y] += sz[x];
com--;
}
}
void pop_edge() {
int x = stk.top().X, y = stk.top().Y; stk.pop();
if(x!=y) {
head[x] = x;
sz[y] -= sz[x];
com++;
}
}
int getcom() {
return com;
}
} dsu;
int n,m,q;
pii p[maxn];
int term[maxn];
int day[maxn];
vector<int> ask[maxn];
vector<pii> edge[maxn*4];
int ord[maxn];
vector<int> wait[maxn];
vector<pii> topping[maxn];
int res[maxn];
map<pii,int> last;
void build(int pos, int l, int r) {
if(l>r) return ;
edge[pos].clear();
if(l==r) return ;
int mid = (l+r)/2;
build(pos<<1,l,mid); build(pos<<1|1,mid+1,r);
}
void update(int pos, int l, int r, int x, int y, pii val) {
if(l>r || r<x || y<l) return ;
if(x<=l && r<=y) {
edge[pos].push_back(val);
return ;
}
int mid = (l+r)/2;
update(pos<<1,l,mid,x,y,val);
update(pos<<1|1,mid+1,r,x,y,val);
}
void solve(int pos, int l, int r) {
for(auto t : edge[pos]) dsu.add_edge(t.X,t.Y);
if(l==r) {
for(auto x : ask[l]) {
// printf("solve t = %d\n",l);
for(auto t : topping[x]) {
dsu.add_edge(t.X,t.Y);
}
res[x] += dsu.getcom();
for(int i=0;i<topping[x].size();++i) dsu.pop_edge();
}
}
else {
int mid = (l+r)/2;
solve(pos<<1,l,mid);
solve(pos<<1|1,mid+1,r);
}
}
bool cmpY(int x, int y) {
return p[x].Y < p[y].Y;
}
bool cmpX(int x, int y) {
return p[x].X > p[y].X;
}
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
) {
n = N; m = T.size(); q = W.size();
for(int i=0;i<m;++i) {
int u = X[i], v = Y[i];
if(u>v) swap(u,v);
if(T[i]==0) {
p[i] = {u,v};
last[{u,v}] = i;
term[i] = m-1;
}
else {
term[last[{u,v}]] = i-1;
}
}
for(int i=0;i<q;++i) day[i] = W[i];
for(int i=0;i<m;++i) ord[i] = i;
dsu.init(n);
//solve L
sort(&ord[0],&ord[m],cmpY);
// for(int i=0;i<m;++i) printf("\t%d %d : %d\n",p[ord[i]].X,p[ord[i]].Y,ord[i]);
build(1,0,m-1);
for(int i=0;i<m;++i) wait[i].clear();
for(int i=0;i<q;++i) {
int l = 0, r = m-1, mid, pos = -1;
while(l<=r) {
mid = (l+r)/2;
if(p[ord[mid]].Y <= P[i]) {
pos = mid;
l = mid+1;
}
else r = mid-1;
}
if(pos!=-1) wait[pos].push_back(i);
else res[i] += n;
// printf("wait %d = %d\n",i,pos);
}
for(int i=0;i<q;++i) topping[i].clear();
for(int id=0;id*sq<m;id++) {
//query
for(int i=id*sq;i<min(m,id*sq+sq);++i) {
for(auto x : wait[i]) {
for(int j=id*sq;j<=i;j++) {
int t = ord[j];
if(T[t]==1) continue;
if(t <= day[x]) topping[x].push_back(p[t]);
}
ask[day[x]].push_back(x);
// printf("\task %d at %d\n",x,day[x]);
}
}
dsu.init(n);
solve(1,0,m-1);
for(int i=id*sq;i<min(m,id*sq+sq);++i) {
for(auto x : wait[i]) ask[day[x]].clear();
}
//updates
for(int i=id*sq;i<min(m,id*sq+sq);++i) {
int x = ord[i];
if(T[x]==1) continue;
update(1,0,m-1,x,term[x],p[x]);
}
}
// printf("-----------------------\n");
//solve R
sort(&ord[0],&ord[m],cmpX);
// for(int i=0;i<m;++i) printf("\t%d %d : %d\n",p[ord[i]].X,p[ord[i]].Y,ord[i]);
build(1,0,m-1);
for(int i=0;i<m;++i) wait[i].clear();
for(int i=0;i<q;++i) {
int l = 0, r = m-1, mid, pos = -1;
while(l<=r) {
mid = (l+r)/2;
if(p[ord[mid]].X > P[i]) {
pos = mid;
l = mid+1;
}
else r = mid-1;
}
if(pos!=-1) wait[pos].push_back(i);
else res[i] += n;
// printf("wait %d = %d\n",i,pos);
}
for(int i=0;i<q;++i) topping[i].clear();
for(int id=0;id*sq<m;id++) {
// printf("id = %d\n",id);
//query
for(int i=id*sq;i<min(m,id*sq+sq);++i) {
for(auto x : wait[i]) {
for(int j=id*sq;j<=i;j++) {
int t = ord[j];
if(T[t]==1) continue;
if(t <= day[x]) topping[x].push_back(p[t]);
}
ask[day[x]].push_back(x);
// printf("\task %d at %d\n",x,day[x]);
}
}
dsu.init(n);
solve(1,0,m-1);
for(int i=id*sq;i<min(m,id*sq+sq);++i) {
for(auto x : wait[i]) ask[day[x]].clear();
}
//updates
for(int i=id*sq;i<min(m,id*sq+sq);++i) {
int x = ord[i];
if(T[x]==1) continue;
update(1,0,m-1,x,term[x],p[x]);
}
}
vector<int> vec;
for(int i=0;i<q;++i) vec.push_back(res[i]-n);
return vec;
}
Compilation message
collapse.cpp: In function 'void solve(int, int, int)':
collapse.cpp:92:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<topping[x].size();++i) dsu.pop_edge();
~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
17532 KB |
Output is correct |
| 2 |
Incorrect |
24 ms |
17532 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
19908 KB |
Output is correct |
| 2 |
Incorrect |
62 ms |
23552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
23552 KB |
Output is correct |
| 2 |
Correct |
76 ms |
24020 KB |
Output is correct |
| 3 |
Correct |
166 ms |
28624 KB |
Output is correct |
| 4 |
Correct |
251 ms |
36268 KB |
Output is correct |
| 5 |
Correct |
885 ms |
184836 KB |
Output is correct |
| 6 |
Correct |
1058 ms |
196424 KB |
Output is correct |
| 7 |
Correct |
7264 ms |
230732 KB |
Output is correct |
| 8 |
Correct |
13085 ms |
237536 KB |
Output is correct |
| 9 |
Correct |
78 ms |
237536 KB |
Output is correct |
| 10 |
Correct |
1020 ms |
237536 KB |
Output is correct |
| 11 |
Correct |
11780 ms |
237536 KB |
Output is correct |
| 12 |
Correct |
13091 ms |
237536 KB |
Output is correct |
| 13 |
Correct |
11822 ms |
238336 KB |
Output is correct |
| 14 |
Correct |
13627 ms |
238336 KB |
Output is correct |
| 15 |
Correct |
11539 ms |
238336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
17532 KB |
Output is correct |
| 2 |
Incorrect |
24 ms |
17532 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
