| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 244312 |
2020-07-03T15:24:53 Z |
MvC |
Collapse (JOI18_collapse) |
C++11 |
|
64 ms |
16492 KB |
#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=300;
const ll mod=1e9+7;
using namespace std;
int n,c,q,t,i,j,x,y,ai,bi,er,p[nmax],sz[nmax],v[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;
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())break;
sort(all(qr[i]));
for(j=1;j<=n;j++)
{
p[j]=j;
sz[j]=1;
}
for(j=0;j<c;j++)
{
v[j]=0;
}
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));
for(j=0;j<lun(vc);j++)
{
v[vc[j].sc.sc]^=1;
}
for(j=0;j<lun(ed[i]);j++)
{
if(v[ed[i][j].sc.sc])
{
b.pb(ed[i][j]);
v[ed[i][j].sc.sc]=0;
}
}
for(j=0;j<lun(ed[i]);j++)if(v[ed[i][j].sc.sc])a.pb(ed[i][j]);
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(s.fd(ed[i][t].fr)!=s.end())s.er(s.fd(ed[i][t].fr));
else s.in(ed[i][j].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(s.fd(ed[i][t].fr)!=s.end())s.er(s.fd(ed[i][t].fr));
else s.in(ed[i][j].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;
}
/*int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n>>c>>q;
for(i=0;i<c;i++)
{
cin>>t>>x>>y;
x++,y++;
if(y>x)swap(x,y);
ed[i/mg].pb(mkp(mkp(x,y),mkp(t,i)));
}
for(i=1;i<=q;i++)
{
cin>>x>>y;
y++;
qr[x/mg].pb(mkp(mkp(y,x%mg),i));
}
for(i=0;i<=c/mg;i++)
{
if(qr[i].empty())break;
sort(all(qr[i]));
for(j=1;j<=n;j++)
{
p[j]=j;
sz[j]=1;
}
for(j=0;j<c;j++)
{
v[j]=0;
}
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));
for(j=0;j<lun(vc);j++)
{
v[vc[j].sc.sc]^=1;
}
for(j=0;j<lun(ed[i]);j++)
{
if(v[ed[i][j].sc.sc])
{
b.pb(ed[i][j]);
v[ed[i][j].sc.sc]=0;
}
}
for(j=0;j<lun(ed[i]);j++)if(v[ed[i][j].sc.sc])a.pb(ed[i][j]);
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(s.fd(ed[i][t].fr)!=s.end())s.er(s.fd(ed[i][t].fr));
else s.in(ed[i][j].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;
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(s.fd(ed[i][t].fr)!=s.end())s.er(s.fd(ed[i][t].fr));
else s.in(ed[i][j].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;
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(i=1;i<=q;i++)cout<<rs[i]<<" ";
cout<<endl;
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
5752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
16492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
16476 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
5752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
