//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include "collapse.h"
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mg=500;
const ll mod=1e9+7;
using namespace std;
int n,c,q,t,i,j,x,y,ai,bi,er,p[nmax],sz[nmax];
vector<pair<int,int> >ed[nmax],vc,a,b;
vector<pair<pair<int,int>,pair<int,int> > >rl;
vector<pair<pair<int,int>,int> >qr[nmax];
set<pair<int,int> >s;
vector<int>rs;
set<pair<int,int> >::iterator it;
map<pair<int,int>,int>v;
int fnd(int x)
{
if(p[x]==x)return x;
return p[x]=fnd(p[x]);
}
void uni(int x,int y,int k)
{
x=fnd(x),y=fnd(y);
if(x==y)return;
if(sz[x]<sz[y])swap(x,y);
if(k)rl.pb(mkp(mkp(y,p[y]),mkp(x,sz[x])));
p[y]=x;
sz[x]+=sz[y];
er++;
}
vector<int> simulateCollapse(int N,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P)
{
n=N,c=lun(T),q=lun(W);
for(i=0;i<c;i++)
{
t=T[i],x=X[i],y=Y[i];
x++,y++;
if(y>x)swap(x,y);
ed[i/mg].pb(mkp(x,y));
}
for(i=0;i<q;i++)
{
x=W[i],y=P[i];
y++;
qr[x/mg].pb(mkp(mkp(y,x%mg),i));
}
rs.resize(q,0);
for(i=0;i<=c/mg;i++)
{
if(qr[i].empty())continue;
sort(all(qr[i]));
for(j=1;j<=n;j++)
{
p[j]=j;
sz[j]=1;
}
vc.clear(),a.clear(),b.clear();
for(j=0;j<i;j++)for(t=0;t<lun(ed[j]);t++)vc.pb(ed[j][t]);
sort(all(vc));
v.clear();
for(j=0;j<lun(vc);j++)
{
v[vc[j]]^=1;
}
for(j=0;j<lun(ed[i]);j++)
{
if(v[ed[i][j]])
{
b.pb(ed[i][j]);
v[ed[i][j]]=0;
}
}
for(j=0;j<lun(vc);j++)
{
if(v[vc[j]])
{
a.pb(vc[j]);
v[vc[j]]=0;
}
}
ai=0;
er=0;
for(j=0;j<lun(qr[i]);j++)
{
for(;ai<lun(a);ai++)
{
if(a[ai].fr>qr[i][j].fr.fr)break;
uni(a[ai].fr,a[ai].sc,0);
}
s.clear();
for(bi=0;bi<lun(b);bi++)
{
if(b[bi].fr>qr[i][j].fr.fr)break;
s.in(b[bi]);
}
for(t=0;t<=qr[i][j].fr.sc;t++)
{
if(ed[i][t].fr>qr[i][j].fr.fr)continue;
if(s.fd(ed[i][t])!=s.end())s.er(s.fd(ed[i][t]));
else s.in(ed[i][t]);
}
rl.clear();
for(it=s.begin();it!=s.end();it++)uni(it->fr,it->sc,1);
rs[qr[i][j].sc]=qr[i][j].fr.fr-er;
reverse(all(rl));
for(t=0;t<lun(rl);t++)
{
p[rl[t].fr.fr]=rl[t].fr.sc;
sz[rl[t].sc.fr]=rl[t].sc.sc;
}
er-=lun(rl);
}
for(j=1;j<=n;j++)
{
p[j]=j;
sz[j]=1;
}
for(j=0;j<lun(a);j++)swap(a[j].fr,a[j].sc);
for(j=0;j<lun(b);j++)swap(b[j].fr,b[j].sc);
sort(all(a));
sort(all(b));
reverse(all(a));
reverse(all(b));
reverse(all(qr[i]));
ai=0;
er=0;
for(j=0;j<lun(qr[i]);j++)
{
for(;ai<lun(a);ai++)
{
if(a[ai].fr<=qr[i][j].fr.fr)break;
uni(a[ai].fr,a[ai].sc,0);
}
s.clear();
for(bi=0;bi<lun(b);bi++)
{
if(b[bi].fr<=qr[i][j].fr.fr)break;
s.in(b[bi]);
}
for(t=0;t<=qr[i][j].fr.sc;t++)
{
if(ed[i][t].sc<=qr[i][j].fr.fr)continue;
if(s.fd(mkp(ed[i][t].sc,ed[i][t].fr))!=s.end())s.er(s.fd(mkp(ed[i][t].sc,ed[i][t].fr)));
else s.in(mkp(ed[i][t].sc,ed[i][t].fr));
}
rl.clear();
for(it=s.begin();it!=s.end();it++)uni(it->fr,it->sc,1);
rs[qr[i][j].sc]+=n-qr[i][j].fr.fr-er;
reverse(all(rl));
for(t=0;t<lun(rl);t++)
{
p[rl[t].fr.fr]=rl[t].fr.sc;
sz[rl[t].sc.fr]=rl[t].sc.sc;
}
er-=lun(rl);
}
}
return rs;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 2 |
Correct |
10 ms |
5248 KB |
Output is correct |
| 3 |
Correct |
14 ms |
5248 KB |
Output is correct |
| 4 |
Correct |
16 ms |
5248 KB |
Output is correct |
| 5 |
Incorrect |
78 ms |
5496 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
47 ms |
8688 KB |
Output is correct |
| 2 |
Correct |
60 ms |
8556 KB |
Output is correct |
| 3 |
Incorrect |
1735 ms |
12784 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
41 ms |
8564 KB |
Output is correct |
| 2 |
Correct |
68 ms |
8556 KB |
Output is correct |
| 3 |
Correct |
108 ms |
8556 KB |
Output is correct |
| 4 |
Correct |
181 ms |
8532 KB |
Output is correct |
| 5 |
Correct |
2545 ms |
8688 KB |
Output is correct |
| 6 |
Incorrect |
2530 ms |
9720 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
5504 KB |
Output is correct |
| 2 |
Correct |
10 ms |
5248 KB |
Output is correct |
| 3 |
Correct |
14 ms |
5248 KB |
Output is correct |
| 4 |
Correct |
16 ms |
5248 KB |
Output is correct |
| 5 |
Incorrect |
78 ms |
5496 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
