#include "collapse.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
struct DSU
{
vector<int> par;
vector<int> rank;
vector<int> used;
void init(int n)
{
par.clear(); rank.clear(); used.clear();
for(int i=0;i<n;i++)
{
par.pb(i); rank.pb(1);
}
}
int rt(int u)
{
if(par[u]==u) return u;
else return rt(par[u]);
}
bool merge(int u, int v)
{
u=rt(u); v=rt(v);
if(u==v) return false;
if(rank[u]<rank[v]) swap(u,v);
used.pb(u); used.pb(v);
rank[u]+=rank[v];
par[v]=u;
return true;
}
void reset()
{
for(int v:used) par[v]=v,rank[v]=1;
used.clear();
}
};
int ans[123456];
const int C = 800;
int n;
ii rev(ii edge)
{
return mp(n-1-edge.fi,n-1-edge.se);
}
bool cmp(ii a, ii b)
{
if(a.se!=b.se) return a.se<b.se;
else return a.fi<b.fi;
}
void solve(vector<pair<int,pair<int,shared_ptr<vector<ii> > > > > query, vector<ii> fixed)
{
int ptr_fixed = 0;
DSU general; general.init(n); DSU specific; specific.init(n);
int cc=0;
for(auto x:query)
{
int pos = x.fi; int lab = x.se.fi;
while(ptr_fixed<fixed.size()&&fixed[ptr_fixed].se<=pos)
{
cc+=general.merge(fixed[ptr_fixed].fi,fixed[ptr_fixed].se); //amortized O(n)
ptr_fixed++;
}
//O(sqrt(n))
int c=0;
for(auto it: *x.se.se)
{
if(it.se<=pos) c+=specific.merge(general.rt(it.fi),general.rt(it.se));
}
//cerr<<"CC : "<<lab<<' '<<pos<<' '<<cc+c<<'\n';
ans[lab]+=pos+2-(cc+c);
specific.reset();
}
}
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
)
{
vi answer; answer.resize(int(W.size())); n=N;
set<ii> curset; //set of current paths
vector<pair<int,ii> > queries;
for(int i=0;i<T.size();i++)
{
if(X[i]>Y[i]) swap(X[i],Y[i]);
}
for(int i=0;i<W.size();i++)
{
queries.pb(mp(W[i],mp(P[i],i)));
}
sort(queries.begin(),queries.end());
int curptr = 0;
for(int l=0;l<T.size();l+=C) //O(sqrt(N))
{
int r = min(l+C-1,int(T.size())-1);
//solve all queries where l<=W<=r
set<ii> fixed = curset; //stores the edges that wont be changed this block
set<ii> change; //stores the set of edges that will be changed this block
for(int i=l;i<=r;i++) change.insert(mp(X[i],Y[i]));
set<ii> dynamic; //stores the current progress of the edges changed in this block
for(auto edge:change)
{
if(fixed.find(edge)!=fixed.end())
{
fixed.erase(edge); dynamic.insert(edge);
}
}
vector<pair<int,pair<int,shared_ptr<vector<ii> > > > > query1,query2;
for(int i=l;i<=r;i++) //O(sqrt(N))
{
if(!T[i])
{
curset.insert(mp(X[i],Y[i])); dynamic.insert(mp(X[i],Y[i]));
}
else
{
curset.erase(mp(X[i],Y[i])); dynamic.erase(mp(X[i],Y[i]));
}
shared_ptr<vector<ii> > p1(new vector<ii>), p2(new vector<ii>); //shared_ptr new trick acquired
for(auto edge:dynamic) //O(sqrt(N))
{
p1->pb(edge);
p2->pb(rev(edge));
}
while(curptr<queries.size()&&queries[curptr].fi<=i)
{
query1.pb(mp(queries[curptr].se.fi,mp(queries[curptr].se.se, p1)));
query2.pb(mp(n-2-queries[curptr].se.fi,mp(queries[curptr].se.se, p2)));
curptr++;
}
}
sort(query1.begin(),query1.end());
sort(query2.begin(),query2.end()); //hope shared pointer doesn't get sorted
vector<ii> fixed2;
for(auto x:fixed) fixed2.pb(x);
sort(fixed2.begin(),fixed2.end(),cmp);
solve(query1, fixed2);
for(auto x:fixed2) {x.fi=n-1-x.fi; x.se=n-1-x.se; swap(x.fi,x.se);}
sort(fixed2.begin(),fixed2.end(),cmp);
solve(query2, fixed2);
}
for(int i=0;i<answer.size();i++) answer[i]=ans[i];
return answer;
}
Compilation message
collapse.cpp: In function 'void solve(std::vector<std::pair<int, std::pair<int, std::shared_ptr<std::vector<std::pair<int, int> > > > > >, std::vector<std::pair<int, int> >)':
collapse.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ptr_fixed<fixed.size()&&fixed[ptr_fixed].se<=pos)
~~~~~~~~~^~~~~~~~~~~~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:108:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<T.size();i++)
~^~~~~~~~~
collapse.cpp:112:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<W.size();i++)
~^~~~~~~~~
collapse.cpp:118:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int l=0;l<T.size();l+=C) //O(sqrt(N))
~^~~~~~~~~
collapse.cpp:150:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(curptr<queries.size()&&queries[curptr].fi<=i)
~~~~~~^~~~~~~~~~~~~~~
collapse.cpp:167:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<answer.size();i++) answer[i]=ans[i];
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
15216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
15616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
