#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
int n;
vector< pair<int/*cut*/,int/*id*/> >seen[nmax];
set< pair<int,int> > edges;
int parent[nmax],sz[nmax];
int root(int node)
{
while(parent[node]!=node)node=parent[node];
return node;
}
pair<int/*big*/,int/*small*/> mem[nmax];
int pointer=0;
void my_merge(int u,int v)
{
/*
cout<<"my_merge "<<u<<" "<<v<<endl;
for(int i=0;i<n;i++)cout<<root(i)<<" ";cout<<endl;
*/
u=root(u);
v=root(v);
if(u==v)return;
if(sz[u]<sz[v])swap(u,v);
mem[pointer]={u,v};
pointer++;
parent[v]=u;
sz[u]+=sz[v];
}
vector<int> other_edge[nmax];
void init()
{
for(int i=0;i<n;i++)
{
sz[i]=1;
parent[i]=i;
other_edge[i]={};
}
pointer=0;
}
set<pair<int,int> > forced,cut;
struct info
{
int cut_line,when,id;
};
vector<info> active={};
bool cmp(info a,info b)
{
return a.cut_line<b.cut_line;
}
bool cmp_2(info a,info b)
{
return a.cut_line>b.cut_line;
}
void pop_pointer(int to)
{
while(pointer>to)
{
pointer--;
sz[mem[pointer].first]-=sz[mem[pointer].second];
parent[mem[pointer].second]=mem[pointer].second;
}
}
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;
for(int i=0;i<W.size();i++)
seen[W[i]].push_back({P[i],i});
int C=T.size();
for(int i=0;i<C;i++)
if(X[i]>Y[i])swap(X[i],Y[i]);
vector<int> outp(W.size(),N);
int BLOCK_SIZE=sqrt(C)+1;
for(int i=0;i<C;i+=BLOCK_SIZE)
{
init();
int STOP=T.size()-1;
STOP=min(STOP,i+BLOCK_SIZE-1);
forced=edges;
cut={};
for(int j=i;j<=STOP;j++)
if(T[j]==1&&forced.count({X[i],Y[i]}))
{
forced.erase({X[j],Y[j]});
cut.insert({X[j],Y[j]});
}
/*
cout<<"forced: "<<endl;
for(auto k:forced)cout<<k.first<<" "<<k.second<<endl;
cout<<"---"<<endl;
*/
active={};
for(int t=i;t<=STOP;t++)
for(auto k:seen[t])
{
info cur;
cur.cut_line=k.first;
cur.id=k.second;
cur.when=t;
active.push_back(cur);
}
sort(active.begin(),active.end(),cmp);
for(auto k:forced)
other_edge[k.second].push_back(k.first);
int j=-1;
for(auto k:active)
{
while(j<k.cut_line)
{
j++;
for(auto p:other_edge[j])
my_merge(p,j);
}
set< pair<int,int> > cur_cut=cut;
for(int j=i;j<=k.when;j++)
if(T[j]==0)cur_cut.insert({X[j],Y[j]});
else cur_cut.erase({X[j],Y[j]});
/*
cout<<k.cut_line<<" "<<k.when<<" "<<k.id<<" j= "<<j<<endl;
cout<<"cur_cut: "<<endl;
for(auto p:cur_cut)cout<<p.first<<" "<<p.second<<endl;
*/
int mem_pointer=pointer;
for(auto p:cur_cut)
if(p.first<=k.cut_line&&p.second<=k.cut_line)
my_merge(p.first,p.second);
/*
cout<<"pointer= "<<pointer<<endl;
cout<<"---"<<endl;
*/
outp[k.id]-=pointer;
pop_pointer(mem_pointer);
}
/*
cout<<i<<" : "<<endl;
for(auto k:edges)cout<<k.first<<" "<<k.second<<endl;
*/
init();
sort(active.begin(),active.end(),cmp_2);
for(auto k:forced)
other_edge[k.first].push_back(k.second);
//cout<<"---\n---\n---\n"<<endl;
j=n;
for(auto k:active)
{
while(j-1>k.cut_line)
{
j--;
for(auto p:other_edge[j])
my_merge(p,j);
}
set< pair<int,int> > cur_cut=cut;
for(int j=i;j<=k.when;j++)
if(T[j]==0)cur_cut.insert({X[j],Y[j]});
else cur_cut.erase({X[j],Y[j]});
/*
cout<<k.cut_line<<" "<<k.when<<" "<<k.id<<" j= "<<j<<endl;
cout<<"cur_cut: "<<endl;
for(auto p:cur_cut)cout<<p.first<<" "<<p.second<<endl;
*/
int mem_pointer=pointer;
for(auto p:cur_cut)
if(p.first>k.cut_line&&p.second>k.cut_line)
my_merge(p.first,p.second);
/*
cout<<"pointer= "<<pointer<<endl;
cout<<"---"<<endl;
*/
outp[k.id]-=pointer;
pop_pointer(mem_pointer);
}
for(int j=i;j<=STOP;j++)
if(T[j]==0)edges.insert({X[j],Y[j]});
else edges.erase({X[j],Y[j]});
}
return outp;
}
/*
int main()
{
int N, C, Q;
scanf("%d%d%d", &N, &C, &Q);
std::vector<int> T(C), X(C), Y(C);
for(int i = 0; i < C; i++) {
scanf("%d%d%d", &T[i], &X[i], &Y[i]);
}
std::vector<int> W(Q), P(Q);
for(int i = 0; i < Q; i++) {
scanf("%d%d", &W[i], &P[i]);
}
auto res = simulateCollapse(N, T, X, Y, W, P);
for(auto i : res) {
printf("%d\n", i);
}
}
*/
Compilation message
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:95:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i=0;i<W.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 2 |
Correct |
9 ms |
5248 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
5248 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
10476 KB |
Output is correct |
| 2 |
Incorrect |
71 ms |
9396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
10476 KB |
Output is correct |
| 2 |
Correct |
81 ms |
9144 KB |
Output is correct |
| 3 |
Correct |
92 ms |
9192 KB |
Output is correct |
| 4 |
Correct |
139 ms |
9064 KB |
Output is correct |
| 5 |
Correct |
219 ms |
8704 KB |
Output is correct |
| 6 |
Correct |
678 ms |
9464 KB |
Output is correct |
| 7 |
Correct |
4860 ms |
20252 KB |
Output is correct |
| 8 |
Correct |
7215 ms |
24292 KB |
Output is correct |
| 9 |
Correct |
71 ms |
11756 KB |
Output is correct |
| 10 |
Correct |
324 ms |
9984 KB |
Output is correct |
| 11 |
Correct |
7925 ms |
27296 KB |
Output is correct |
| 12 |
Correct |
9190 ms |
27476 KB |
Output is correct |
| 13 |
Correct |
8257 ms |
27224 KB |
Output is correct |
| 14 |
Correct |
9207 ms |
27668 KB |
Output is correct |
| 15 |
Correct |
8266 ms |
27268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 2 |
Correct |
9 ms |
5248 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
5248 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
