Submission #1278240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278240		PieArmy	Unique Cities (JOI19_ho_t5)	C++20	100 / 100	315 ms	25548 KiB

joi2019_ho_t5

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;

int n,m,s;
vector<int>komsu[200023];
int arr[200023];
vector<int>dia;
int root[200023],par[200023];
int dep[200023],h[200023],h2[200023];
int uniq[200023];

int fir[200023];
vector<int>v;
int ans[200023];

void dfs(int pos,int k){
	int k2=k;
	int l=0,r=k;
	while(l<r){
		int mi=(l+r)/2;
		if(root[v[mi]])l=mi+1;
		else if(dep[v[mi]]>=dep[pos]-h2[pos])r=mi;
		else l=mi+1;
	}
	k2=l;
	pair<int,int> old={-1,1e9};
	int old2=1e9;
	if(fir[arr[pos]]>=k2){
		old.sc=fir[arr[pos]];
		if(k2==v.size()){
			old.fr=-2;
			v.pb(pos);
		}
		else{
			old.fr=v[k2];
			old2=fir[arr[old.fr]];
			if(k2==old2){
				fir[arr[old.fr]]=1e9;
			}
			v[k2]=pos;
		}
		fir[arr[pos]]=k2;
		k2++;
	}
	int y=-1;
	for(int x:komsu[pos]){
		if(x==par[pos])continue;
		if(root[x])continue;
		if(h[x]==h[pos]-1){
			y=x;
			dfs(y,k2);
			break;
		}
	}
	if(old.fr!=-1){
		fir[arr[pos]]=old.sc;
		if(old.fr==-2){
			v.pop_back();
		}
		else{
			v[--k2]=old.fr;
			fir[arr[old.fr]]=old2;
		}
	}
	old={-1,1e9};
	old2=1e9;
	l=0;r=k;
	while(l<r){
		int mi=(l+r)/2;
		if(root[v[mi]])l=mi+1;
		else if(dep[v[mi]]>=dep[pos]-h[pos])r=mi;
		else l=mi+1;
	}
	k2=l;
	ans[pos]=k2;
	if(fir[arr[pos]]>=k2){
		old.sc=fir[arr[pos]];
		if(k2==v.size()){
			old.fr=-2;
			v.pb(pos);
		}
		else{
			old.fr=v[k2];
			old2=fir[arr[old.fr]];
			if(k2==old2){
				fir[arr[old.fr]]=1e9;
			}
			v[k2]=pos;
		}
		fir[arr[pos]]=k2;
		k2++;
	}
	for(int x:komsu[pos]){
		if(x==par[pos])continue;
		if(root[x])continue;
		if(x==y)continue;
		dfs(x,k2);
	}
	if(old.fr!=-1){
		fir[arr[pos]]=old.sc;
		if(old.fr==-2){
			v.pop_back();
		}
		else{
			v[--k2]=old.fr;
			fir[arr[old.fr]]=old2;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		komsu[x].pb(y);
		komsu[y].pb(x);
	}
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	{
		int a=1;
		queue<int>q;
		q.push(1);
		while(q.size()){
			int pos=q.front();
			q.pop();
			a=pos;
			for(int x:komsu[pos]){
				if(x==par[pos])continue;
				par[x]=pos;
				q.push(x);
			}
		}
		int b=a;
		q.push(a);
		par[a]=a;
		while(q.size()){
			int pos=q.front();
			q.pop();
			b=pos;
			for(int x:komsu[pos]){
				if(x==par[pos])continue;
				dep[x]=dep[pos]+1;
				par[x]=pos;
				q.push(x);
			}
		}
		while(b!=a){
			dia.pb(b);
			root[b]=1;
			b=par[b];
		}
		dia.pb(a);
		root[a]=1;
		reverse(dia.begin(),dia.end());
	}
	s=dia.size();
	{
		function<void(int)>find_h=[&](int pos)->void{
			h[pos]=0;
			h2[pos]=0;
			for(int x:komsu[pos]){
				if(x==par[pos])continue;
				if(root[x])continue;
				find_h(x);
				if(h[x]+1>h[pos]){
					h2[pos]=h[pos];
					h[pos]=h[x]+1;
				}
				else if(h[x]+1>h2[pos]){
					h2[pos]=h[x]+1;
				}
			}
		};
		for(int x:dia){
			find_h(x);
		}
	}
	{
		int mx=-1;
		for(int i=0;i<s;i++){
			if(mx<i){
				uniq[dia[i]]=1;
			}
			mx=max(mx,i+h[dia[i]]);
		}
	}
	for(int i=1;i<=m;i++){
		fir[i]=1e9;
	}
	int p=s-1;
	for(int o=s-1;o>=0;o--){
		if(o*2>=s)continue;
		int bas=dia[o];
		while(o<p-o){
			if(uniq[dia[p]]){
				if(fir[arr[dia[p]]]==1e9){
					fir[arr[dia[p]]]=v.size();
					v.pb(dia[p]);
				}
			}
			p--;
		}
		root[bas]=0;
		dfs(bas,v.size());
		root[bas]=1;
	}
	v.clear();
	for(int i=1;i<=m;i++){
		fir[i]=1e9;
	}
	{
		for(int i=1;i<=n;i++){
			uniq[i]=0;
		}
		int mn=s;
		for(int i=s-1;i>=0;i--){
			if(mn>i){
				uniq[dia[i]]=1;
			}
			mn=min(mn,i-h[dia[i]]);
		}
	}
	p=0;
	for(int o=0;o<s;o++){
		if(o*2<s)continue;
		int bas=dia[o];
		while(s-1-o<o-p){
			if(uniq[dia[p]]){
				if(fir[arr[dia[p]]]==1e9){
					fir[arr[dia[p]]]=v.size();
					v.pb(dia[p]);
				}
			}
			p++;
		}
		root[bas]=0;
		dfs(bas,v.size());
		root[bas]=1;
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
}

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