| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 377668 |
2021-03-14T16:50:43 Z |
YJU |
Collapse (JOI18_collapse) |
C++14 |
|
5258 ms |
17604 KB |
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll N=1e5+5;
const ll K=sqrt(N);
const ll MOD2=998244353;
const ld pi=acos(-1);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
ll sz[N],dir[N],now,stk[N][2],cnt;
ll find(ll id){
while(id!=dir[id])id=dir[id];
return id;
}
void Union(ll nda,ll ndb){
nda=find(nda);ndb=find(ndb);
if(nda==ndb)return ;
if(sz[nda]>sz[ndb])swap(nda,ndb);
//merge nda to ndb
++now;--cnt;
stk[now][0]=nda;stk[now][1]=ndb;
sz[ndb]+=sz[nda];
dir[nda]=ndb;
}
void restore(ll T){
while(now>T){
ll nda=stk[now][0],ndb=stk[now][1];
sz[ndb]-=sz[nda];
dir[nda]=nda;
--now;++cnt;
}
}
set<pll> Edge,init;
ll n,q,c;
ll ty[N],x[N],y[N],w[N],p[N],ans[N];
vector<pll> oper[N];
vector<ll> query[N],Q[N];
void solve(){
//reset
now=cnt=0;
REP1(i,n)sz[i]=1,dir[i]=i;
REP(i,q){Q[w[i]].pb(i);}
for(ll start=0;start<c;start+=K){
/**/
Edge.clear();
init.clear();
/**/
for(ll i=0;i<start;i++){
if(ty[i]==0){
Edge.insert(mp(x[i],y[i]));
}else{
Edge.erase(mp(x[i],y[i]));
}
}
for(ll i=start;i<min(c,start+K);i++){
if(ty[i]==1&&Edge.find(mp(x[i],y[i]))!=Edge.end()){
Edge.erase(mp(x[i],y[i]));
init.insert(mp(x[i],y[i]));
}
for(ll j:Q[i]){
query[p[j]].pb(j);
}
/**/Q[i].clear();/**/
}
for(auto i:Edge){
oper[i.Y].pb(mp(i.X,i.Y));
}
REP1(i,n){
/*new node*/++cnt;/**/
for(pll j:oper[i]){
Union(j.X,j.Y);
}
for(ll j:query[i]){
/**/ll pos=now;/**/
set<pll> tmp=init;
for(ll ii=start;ii<w[j]+1;ii++){
if(ty[ii]==1)tmp.erase(mp(x[ii],y[ii]));
else tmp.insert(mp(x[ii],y[ii]));
}
for(pll ii:tmp){
if(ii.Y<=i){
Union(ii.X,ii.Y);
}
}
ans[j]+=cnt;
/**/restore(pos);/**/
}
/**/
oper[i].clear();
query[i].clear();
/**/
}
}
}
void rev(){
REP(i,c){
ll xx=x[i],yy=y[i];
x[i]=n+1-yy;
y[i]=n+1-xx;
}
REP(i,q){
p[i]=n-p[i];
}
}
void out(){
REP(i,c)assert(x[i]<y[i]),assert(x[i]<=n&&x[i]>=1),assert(y[i]<=n&&y[i]>=1);
//REP(i,c)cout<<ty[i]<<" "<<x[i]<<" "<<y[i]<<"\n";
//REP(i,q)cout<<p[i]<<" "<<w[i]<<"\n";
}
vector<ll> simulateCollapse(ll _n,vector<ll> _ty,vector<ll> _x,vector<ll> _y,vector<ll> _w,vector<ll> _p){
n=_n;q=SZ(_w);c=SZ(_ty);
REP(i,c){
ty[i]=_ty[i];x[i]=_x[i]+1;y[i]=_y[i]+1;
if(x[i]>y[i])swap(x[i],y[i]);
}
REP(i,q){p[i]=_p[i]+1;w[i]=_w[i];}
out();
solve();
rev();
out();
solve();
vector<ll> ret;
REP(i,q)ret.pb(ans[i]);
return ret;
}
/*
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
vector<ll> T={0,0,0,0,0,0,1,0};
vector<ll> TX={0,0,1,2,4,4,4,4};
vector<ll> TY={1,3,2,4,0,3,3,3};
vector<ll> W={7};
vector<ll> P={3};
vector<ll> ans=simulateCollapse(5,T,TX,TY,W,P);
for(auto i:ans)cout<<i<<"\n";
return 0;
}
//*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
7916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
11752 KB |
Output is correct |
| 2 |
Correct |
71 ms |
12388 KB |
Output is correct |
| 3 |
Incorrect |
5258 ms |
17604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
11752 KB |
Output is correct |
| 2 |
Correct |
77 ms |
11752 KB |
Output is correct |
| 3 |
Correct |
158 ms |
12076 KB |
Output is correct |
| 4 |
Correct |
304 ms |
12268 KB |
Output is correct |
| 5 |
Incorrect |
2320 ms |
12020 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
7916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
