제출 #333225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333225		YJU	Cats or Dogs (JOI18_catdog)	C++14	0 / 100	7 ms	9836 KiB

catdog

#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;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 30
• Subtask 3: 0 / 62