Submission #335633

#	Time	Username	Problem	Language	Result	Execution time	Memory
335633		YJU	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	386 ms	64068 KiB

catdog

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e6+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 sz[N],p[N],vid[N],ip[N],top[N],tseg[N],color[N];
vector<ll> v[N],lis;
queue<ll> q;

ll u[N],a[N],b[N];

struct Segment_Tree{
	vector<ll> u;
	vector<ll> seg[2][2];
	Segment_Tree(vector<ll> tmp):u(tmp){
		REP(i,2)REP(j,2)seg[i][j].resize(4*(SZ(tmp)+1));
		REP(i,SZ(u))ins(1,0,SZ(u),i);
	};
	ll A(){return min(seg[0][0][1],seg[0][1][1]);}
	ll B(){return min(seg[1][0][1],seg[1][1][1]);}
	void ins(ll id,ll l,ll r,ll to){
		if(l==r-1){
			if(color[u[l]]==0){
				seg[0][0][id]=a[u[l]];seg[0][1][id]=seg[1][0][id]=INF;seg[1][1][id]=b[u[l]];
			}else{
				REP(i,2)REP(j,2)seg[i][j][id]=INF;
				seg[color[u[l]]-1][color[u[l]]-1][id]=(color[u[l]]==1?a[u[l]]:b[u[l]]);
			}
			return ;
		}
		ll mid=(l+r)>>1;
		if(to<mid){
			ins(id*2,l,mid,to);
		}else{
			ins(id*2+1,mid,r,to);
		}
		REP(i,2)REP(j,2){
			seg[i][j][id]=INF;
			REP(ii,2)REP(jj,2)seg[i][j][id]=min(seg[i][j][id],seg[i][ii][id*2]+seg[jj][j][id*2+1]+(ii==jj?0:1));
		}
	}
	void upd(ll to){
		ins(1,0,SZ(u),to);
	}
};

vector<Segment_Tree> vseg;
 
/*void DFS(ll nd,ll pa){
	dp[nd][1]=dp[nd][2]=0;
	for(auto i:v[nd]){
		if(i==pa)continue;
		DFS(i,nd);
		dp[nd][1]+=min(dp[i][1],dp[i][2]+1);
		dp[nd][2]+=min(dp[i][2],dp[i][1]+1);
	}
	if(col[nd]){dp[nd][3-col[nd]]=INF;}
}*/

void build(){
	function<void(int,int)> predfs=[&](int nd,int pa){
		sz[nd]=1;p[nd]=pa;vid[nd]=0;
		for(int i:v[nd]){
			if(i==pa)continue;
			predfs(i,nd);
			sz[nd]+=sz[i];
			if(sz[vid[nd]]<sz[i])vid[nd]=i;
		}
	};
	predfs(1,0);
	q.push(1);
	while(SZ(q)){
		ll x=q.front();q.pop();
		lis.clear();
		top[x]=x;lis.pb(x);
		while(vid[x]){
			for(int i:v[x])if(i!=p[x]&&i!=vid[x])q.push(i);
			lis.pb(vid[x]);top[vid[x]]=top[x];
			x=vid[x];
		}
		vseg.pb(Segment_Tree(lis));
		REP(i,SZ(lis))ip[lis[i]]=i,tseg[lis[i]]=SZ(vseg)-1;
	}
}

void update(ll nd){
	while(nd){
		a[p[top[nd]]]-=min(vseg[tseg[nd]].A(),vseg[tseg[nd]].B()+1);
		b[p[top[nd]]]-=min(vseg[tseg[nd]].A()+1,vseg[tseg[nd]].B());
		vseg[tseg[nd]].upd(ip[nd]);
		a[p[top[nd]]]+=min(vseg[tseg[nd]].A(),vseg[tseg[nd]].B()+1);
		b[p[top[nd]]]+=min(vseg[tseg[nd]].A()+1,vseg[tseg[nd]].B());
		nd=p[top[nd]];
	}
} 
 
void initialize(ll n,vector<ll> ea,vector<ll> eb){
	REP(i,n-1)v[ea[i]].pb(eb[i]),v[eb[i]].pb(ea[i]);
	build();
}
 
ll cat(ll id){
	color[id]=1;
	update(id);
	return min(vseg[0].A(),vseg[0].B());
}
 
ll dog(ll id){
	color[id]=2;
	update(id);
	return min(vseg[0].A(),vseg[0].B());
}
 
ll neighbor(ll id){
	color[id]=0;
	update(id);
	return min(vseg[0].A(),vseg[0].B());
}
/*
int main(){
	ll n;
	cin>>n;
	vector<ll> ea(n-1),eb(n-1);
	REP(i,n-1)cin>>ea[i]>>eb[i];
	initialize(n,ea,eb);
	return 0;
}*/

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