//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 = 320;
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 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];
void build(int pos, int l, int r) {
for(int i=l;i<=r;i++) edge[i].clear();
}
void update(int pos, int l, int r, int x, int y, pii val) {
edge[x].push_back(val);
}
void solve(int pos, int l, int r) {
if(l==r) {
for(auto t : edge[l]) dsu.add_edge(t.X,t.Y);
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);
p[i] = {u,v};
}
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 <= 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];
update(1,0,m-1,x,m-1,p[x]);
}
}
// printf("-----------------------\n");
dsu.init(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 <= 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];
update(1,0,m-1,x,m-1,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:79: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 |
24 ms |
17404 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
17404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
20032 KB |
Output is correct |
| 2 |
Incorrect |
71 ms |
23920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
23920 KB |
Output is correct |
| 2 |
Correct |
87 ms |
24008 KB |
Output is correct |
| 3 |
Correct |
126 ms |
28508 KB |
Output is correct |
| 4 |
Correct |
208 ms |
36276 KB |
Output is correct |
| 5 |
Correct |
623 ms |
114824 KB |
Output is correct |
| 6 |
Correct |
836 ms |
138372 KB |
Output is correct |
| 7 |
Correct |
3564 ms |
147992 KB |
Output is correct |
| 8 |
Correct |
5607 ms |
151660 KB |
Output is correct |
| 9 |
Correct |
71 ms |
151660 KB |
Output is correct |
| 10 |
Correct |
688 ms |
151660 KB |
Output is correct |
| 11 |
Correct |
6021 ms |
151660 KB |
Output is correct |
| 12 |
Correct |
7258 ms |
153604 KB |
Output is correct |
| 13 |
Correct |
6346 ms |
153604 KB |
Output is correct |
| 14 |
Correct |
6261 ms |
153860 KB |
Output is correct |
| 15 |
Correct |
5847 ms |
153860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
17404 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
17404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
