oj.uz

답안 #536324

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
536324 2022-03-12T22:03:58 Z Jasiekstrz Unique Cities (JOI19_ho_t5) C++17
0 / 100
 783 ms 40200 KB 
#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);
	}

	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);
	}
	//cerr<<x<<" "<<last_fst<<"\n";

	for(auto v:e[x])
	{
		if(v!=p)
		{
			int di=(dd[x][0]==dd[v][0]+1 ? dd[x][1]:dd[x][0]);
			//cerr<<x<<" "<<v<<" "<<di<<"\n";
			block(1,1,P,dep-di,dep-1,x);
			solve(v,x,dep+1);
			unblock(1,1,P,dep-di,dep-1,x);
		}
	}

	if(last_fst!=-1)
	{
		add(fst[tab[x]],-1);
		fst[tab[x]]=last_fst;
	}
	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
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6612 KB Output is correct
2 Incorrect 9 ms 6740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 310 ms 14064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 473 ms 18248 KB Output is correct
2 Correct 783 ms 40200 KB Output is correct
3 Incorrect 69 ms 10576 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6612 KB Output is correct
2 Incorrect 9 ms 6740 KB Output isn't correct
3 Halted 0 ms 0 KB -