#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 = 330;
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);
// printf("\tadd edge %d %d\n",x,y);
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();
// printf("\tpop edge %d %d\n",x,y);
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]) {
for(auto t : topping[x]) {
// printf("\tt %d : topping %d %d\n",l,t.X,t.Y);
dsu.add_edge(t.X,t.Y);
}
res[x] += dsu.getcom();
// printf("solve t = %d => %d\n",l,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);
}
for(int i=0;i<edge[pos].size();i++) dsu.pop_edge();
}
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);
p[i] = {u,v};
if(T[i]==0) {
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++) printf("%d : %d %d\n",i,term[i],T[i]);
for(int i=0;i<m;++i) ord[i] = i;
// printf("-------------------\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++) {
int st = id*sq, ft = min(m,id*sq+sq);
//query
for(int i=st;i<ft;++i) {
for(auto x : wait[i]) {
for(int j=st;j<=i;++j) {
int t = ord[j];
if(T[t]==1) continue;
if(t <= day[x] && day[x]<=term[t]) topping[x].push_back(p[t]);
}
ask[day[x]].push_back(x);
// printf("\task %d at %d\n",x,day[x]);
}
}
solve(1,0,m-1);
for(int i=st;i<ft;++i) {
for(auto x : wait[i]) ask[day[x]].clear();
}
//updates
for(int i=st;i<ft;++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);
int st = id*sq, ft = min(m,id*sq+sq);
//query
for(int i=st;i<ft;++i) {
for(auto x : wait[i]) {
for(int j=st;j<=i;++j) {
int t = ord[j];
if(T[t]==1) continue;
if(t <= day[x] && day[x] <= term[t]) topping[x].push_back(p[t]);
}
ask[day[x]].push_back(x);
// printf("\task %d at %d\n",x,day[x]);
}
}
solve(1,0,m-1);
for(int i=st;i<ft;++i) {
for(auto x : wait[i]) ask[day[x]].clear();
}
//updates
for(int i=st;i<ft;++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:94:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<topping[x].size();++i) dsu.pop_edge();
~^~~~~~~~~~~~~~~~~~
collapse.cpp:102:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<edge[pos].size();i++) dsu.pop_edge();
~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
17144 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
17144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
19860 KB |
Output is correct |
| 2 |
Incorrect |
64 ms |
22892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
22892 KB |
Output is correct |
| 2 |
Incorrect |
82 ms |
24012 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
17144 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
17144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
