#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=1;
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<pair<int,int>,pair<int,int> > >rl,ed[nmax],vc,a,b;
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(mkp(x,y),mkp(t,i)));
}
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].fr]^=1;
}
for(j=0;j<lun(ed[i]);j++)
{
if(v[ed[i][j].fr])
{
b.pb(ed[i][j]);
v[ed[i][j].fr]=0;
}
}
for(j=0;j<lun(vc);j++)if(v[vc[j].fr])a.pb(vc[j]),v[vc[j].fr]=0;
ai=0;
er=0;
for(j=0;j<lun(qr[i]);j++)
{
for(;ai<lun(a);ai++)
{
if(a[ai].fr.fr>qr[i][j].fr.fr)break;
uni(a[ai].fr.fr,a[ai].fr.sc,0);
}
s.clear();
for(bi=0;bi<lun(b);bi++)
{
if(b[bi].fr.fr>qr[i][j].fr.fr)break;
s.in(b[bi].fr);
}
for(t=0;t<=qr[i][j].fr.sc;t++)
{
if(ed[i][t].fr.fr>qr[i][j].fr.fr)continue;
if(s.fd(ed[i][t].fr)!=s.end())s.er(s.fd(ed[i][t].fr));
else s.in(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]=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.fr,a[j].fr.sc);
for(j=0;j<lun(b);j++)swap(b[j].fr.fr,b[j].fr.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.fr<=qr[i][j].fr.fr)break;
uni(a[ai].fr.fr,a[ai].fr.sc,0);
}
s.clear();
for(bi=0;bi<lun(b);bi++)
{
if(b[bi].fr.fr<=qr[i][j].fr.fr)break;
s.in(b[bi].fr);
}
for(t=0;t<=qr[i][j].fr.sc;t++)
{
if(ed[i][t].fr.sc<=qr[i][j].fr.fr)continue;
if(s.fd(mkp(ed[i][t].fr.sc,ed[i][t].fr.fr))!=s.end())s.er(s.fd(mkp(ed[i][t].fr.sc,ed[i][t].fr.fr)));
else s.in(mkp(ed[i][t].fr.sc,ed[i][t].fr.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 |
786 ms |
6056 KB |
Output is correct |
2 |
Correct |
10 ms |
5248 KB |
Output is correct |
3 |
Correct |
10 ms |
5376 KB |
Output is correct |
4 |
Correct |
11 ms |
5248 KB |
Output is correct |
5 |
Correct |
1159 ms |
6048 KB |
Output is correct |
6 |
Correct |
3216 ms |
6668 KB |
Output is correct |
7 |
Correct |
10 ms |
5376 KB |
Output is correct |
8 |
Correct |
10 ms |
5376 KB |
Output is correct |
9 |
Correct |
1577 ms |
6264 KB |
Output is correct |
10 |
Correct |
2035 ms |
6400 KB |
Output is correct |
11 |
Correct |
3151 ms |
6456 KB |
Output is correct |
12 |
Correct |
3094 ms |
6656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
8812 KB |
Output is correct |
2 |
Correct |
41 ms |
9400 KB |
Output is correct |
3 |
Execution timed out |
15069 ms |
16596 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
8556 KB |
Output is correct |
2 |
Correct |
50 ms |
8848 KB |
Output is correct |
3 |
Correct |
64 ms |
9212 KB |
Output is correct |
4 |
Correct |
53 ms |
9372 KB |
Output is correct |
5 |
Correct |
101 ms |
9116 KB |
Output is correct |
6 |
Correct |
5391 ms |
10992 KB |
Output is correct |
7 |
Execution timed out |
15064 ms |
16224 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
786 ms |
6056 KB |
Output is correct |
2 |
Correct |
10 ms |
5248 KB |
Output is correct |
3 |
Correct |
10 ms |
5376 KB |
Output is correct |
4 |
Correct |
11 ms |
5248 KB |
Output is correct |
5 |
Correct |
1159 ms |
6048 KB |
Output is correct |
6 |
Correct |
3216 ms |
6668 KB |
Output is correct |
7 |
Correct |
10 ms |
5376 KB |
Output is correct |
8 |
Correct |
10 ms |
5376 KB |
Output is correct |
9 |
Correct |
1577 ms |
6264 KB |
Output is correct |
10 |
Correct |
2035 ms |
6400 KB |
Output is correct |
11 |
Correct |
3151 ms |
6456 KB |
Output is correct |
12 |
Correct |
3094 ms |
6656 KB |
Output is correct |
13 |
Correct |
40 ms |
8812 KB |
Output is correct |
14 |
Correct |
41 ms |
9400 KB |
Output is correct |
15 |
Execution timed out |
15069 ms |
16596 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |