Submission #536328

#	Time	Username	Problem	Language	Result	Execution time	Memory
536328		Jasiekstrz	Unique Cities (JOI19_ho_t5)	C++17	100 / 100	793 ms	45644 KiB

joi2019_ho_t5

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
const int P=(1<<18);
vector<int> e[N+10];
int tab[N+10];
int dd[N+10][2];
int fst[N+10];
int tr[2*P+10];
int clr[2*P+10];
int val[2*P+10];
bool myturn[N+10];
int out[N+10];
void add(int x,int c)
{
	for(x+=P-1;x>0;x/=2)
	{
		if(clr[x]!=0)
			break;
		tr[x]+=c;
	}
	return;
}
void block(int i,int l,int r,int ls,int rs,int id)
{
	if(clr[i]!=0 || rs<l || r<ls)
		return;
	if(ls<=l && r<=rs)
	{
		clr[i]=id;
		val[i]=tr[i];
		tr[i]=0;
		return;
	}
	int mid=(l+r)/2;
	block(2*i,l,mid,ls,rs,id);
	block(2*i+1,mid+1,r,ls,rs,id);
	tr[i]=tr[2*i]+tr[2*i+1];
	return;
}
void unblock(int i,int l,int r,int ls,int rs,int id)
{
	if(clr[i]==id)
	{
		clr[i]=0;
		tr[i]=val[i];
		return;
	}
	if(clr[i]!=0 || rs<l || r<ls)
		return;
	int mid=(l+r)/2;
	unblock(2*i,l,mid,ls,rs,id);
	unblock(2*i+1,mid+1,r,ls,rs,id);
	tr[i]=tr[2*i]+tr[2*i+1];
	return;
}
bool is_on(int x)
{
	for(x+=P-1;x>0;x/=2)
	{
		if(clr[x]!=0)
			return false;
	}
	return true;
}
pair<int,int> dfs_far(int x,int p)
{
	pair<int,int> ans={-1,x};
	for(auto v:e[x])
	{
		if(v!=p)
			ans=max(ans,dfs_far(v,x));
	}
	ans.fi++;
	return ans;
}
void dfs_dep(int x,int p,vector<int> &ans)
{
	ans[x]=ans[p]+1;
	for(auto v:e[x])
	{
		if(v!=p)
			dfs_dep(v,x,ans);
	}
	return;
}
void dfs_dd(int x,int p)
{
	dd[x][0]=dd[x][1]=0;
	for(auto v:e[x])
	{
		if(v!=p)
		{
			dfs_dd(v,x);
			if(dd[v][0]+1>dd[x][0])
			{
				dd[x][1]=dd[x][0];
				dd[x][0]=dd[v][0]+1;
			}
			else if(dd[v][0]+1>dd[x][1])
				dd[x][1]=dd[v][0]+1;
		}
	}
	return;
}
void solve(int x,int p,int dep)
{
	if(myturn[x])
	{
		block(1,1,P,dep-dd[x][0],dep-1,x);
		out[x]=tr[1];
		unblock(1,1,P,dep-dd[x][0],dep-1,x);
	}

	for(auto v:e[x])
	{
		if(v!=p)
		{
			int di=(dd[x][0]==dd[v][0]+1 ? dd[x][1]:dd[x][0]);
			block(1,1,P,dep-di,dep-1,x);
			int last_fst=-1;
			if(fst[tab[x]]==0 || !is_on(fst[tab[x]]))
			{
				last_fst=fst[tab[x]];
				fst[tab[x]]=dep;
				add(fst[tab[x]],1);
			}

			solve(v,x,dep+1);

			if(last_fst!=-1)
			{
				add(fst[tab[x]],-1);
				fst[tab[x]]=last_fst;
			}
			unblock(1,1,P,dep-di,dep-1,x);
		}
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
		cin>>tab[i];
	int dia[2];
	dia[0]=dfs_far(1,0).se;
	dia[1]=dfs_far(dia[0],0).se;
	//cerr<<dia[0]<<" "<<dia[1]<<"\n";
	vector<int> diadep[2];
	for(int i:{0,1})
	{
		diadep[i].resize(N+10);
		diadep[i][0]=0;
		dfs_dep(dia[i],0,diadep[i]);
		//for(int j=1;j<=n;j++)
		//	cerr<<diadep[i][j]<<" \n"[j==n];
	}
	for(bool it:{0,1})
	{
		for(int i=1;i<=n;i++)
		{
			myturn[i]=(diadep[it][i]>=diadep[!it][i]);
			//cerr<<i<<" "<<myturn[i]<<"\n";
		}
		dfs_dd(dia[it],0);
		solve(dia[it],0,1);
	}
	for(int i=1;i<=n;i++)
		cout<<out[i]<<"\n";
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32