//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];
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;
while(!stk.empty()) stk.pop();
}
void add_edge(int u, int v) {
int x = findhead(u), y = findhead(v);
stk.push({x,y});
head[x] = y;
if(x!=y) com--;
}
void pop_edge() {
int x = stk.top().X, y = stk.top().Y; stk.pop();
head[x] = x;
if(x!=y) 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) {
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);
}
int tmp = edge[pos].size();
for(int i=0;i<tmp;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};
}
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]);
}
}
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]);
}
}
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:80: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 |
38 ms |
17656 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
17656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
20028 KB |
Output is correct |
| 2 |
Incorrect |
72 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
70 ms |
23900 KB |
Output is correct |
| 3 |
Correct |
116 ms |
28388 KB |
Output is correct |
| 4 |
Correct |
177 ms |
36180 KB |
Output is correct |
| 5 |
Correct |
799 ms |
114696 KB |
Output is correct |
| 6 |
Correct |
1574 ms |
138740 KB |
Output is correct |
| 7 |
Execution timed out |
15070 ms |
138740 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
17656 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
17656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
