| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 333224 | YJU | Cats or Dogs (JOI18_catdog) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=4e5+5;
const ll K=350;
const ld pi=acos(-1);
const long long INF=(1LL<<28);
#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 seg[4*N],ti,exist[N],ip[N],nl[N],nr[N],pa[N],cnt[2],sum;
vector<ll> v[N],lis;
void ins(ll id,ll l,ll r,ll to,ll d){
if(l==r-1){seg[id]+=d;return ;}
ll mid=(l+r)>>1;
if(to<mid){
ins(id*2,l,mid,to,d);
}else{
ins(id*2+1,mid,r,to,d);
}
seg[id]=seg[id*2]+seg[id*2+1];
}
ll q(ll id,ll l,ll r,ll ql,ll qr){
if(l>=ql&&r<=qr)return seg[id];
if(l>=qr||r<=ql)return 0;
ll mid=(l+r)>>1;
return q(id*2,l,mid,ql,qr)+q(id*2+1,mid,r,ql,qr);
}
void upd(ll nd,ll ty){
ll ti=q(1,0,N,nl[nd],nr[nd])+exist[pa[nd]];
exist[nd]=(ty>0?1:0);
sum-=ty*(ti-1);
ins(1,0,n,ip[nd],ty);
}
void initialize(int n,vector<int> a,vector<int> b){
REP(i,n-1)v[a[i]*2].pb(b[i]*2),v[b[i]*2].pb(a[i]*2),v[a[i]*2-1].pb(b[i]*2-1),v[b[i]*2-1].pb(a[i]*2-1);
lis.pb(1);ip[1]=ti++;exist[1]=1;
REP(i,n){
nl[lis[i]]=ti;
for(auto j:v[lis[i]]){
if(exist[j])continue;
lis.pb(j);ip[j]=ti++;exist[j]=1;
}
nr[lis[i]]=ti;
}
lis.clear();
lis.pb(2);ip[2]=ti++;exist[2]=1;
REP(i,n){
nl[lis[i]]=ti;
for(auto j:v[lis[i]]){
if(exist[j])continue;
lis.pb(j);ip[j]=ti++;exist[j]=1;
}
nr[lis[i]]=ti;
}
REP(i,2*n)ins(1,0,N,i,1);
sum=2;
}
int cat(int id){
upd(id*2-1,-1);
++cnt[0];
if(cnt[0]==0||cnt[1]==0)return 0;
return sum-1;
}
int dog(int id){
upd(id*2,-1);
++cnt[1];
if(cnt[0]==0||cnt[1]==0)return 0;
return sum-1;
}
int neighbor(int id){
if(!exist[id*2])upd(id*2,1),--cnt[1];
else if(!exist[id*2-1])upd(id*2-1,1),--cnt[0];
if(cnt[0]==0||cnt[1]==0)return 0;
return sum-1;
}