oj.uz

Submission #536325

# Submission time Handle Problem Language Result Execution time Memory
536325 2022-03-12T22:08:05 Z Jasiekstrz Unique Cities (JOI19_ho_t5) C++17
32 / 100
 766 ms 42392 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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Incorrect 6 ms 6740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 300 ms 12468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 15292 KB Output is correct
2 Correct 755 ms 36556 KB Output is correct
3 Correct 79 ms 9900 KB Output is correct
4 Correct 584 ms 21492 KB Output is correct
5 Correct 766 ms 42392 KB Output is correct
6 Correct 728 ms 30952 KB Output is correct
7 Correct 557 ms 21388 KB Output is correct
8 Correct 654 ms 25744 KB Output is correct
9 Correct 625 ms 24248 KB Output is correct
10 Correct 630 ms 23028 KB Output is correct
11 Correct 579 ms 21672 KB Output is correct
12 Correct 717 ms 38296 KB Output is correct
13 Correct 645 ms 30400 KB Output is correct
14 Correct 651 ms 30628 KB Output is correct
15 Correct 451 ms 22092 KB Output is correct
16 Correct 639 ms 35108 KB Output is correct
17 Correct 651 ms 31140 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Incorrect 6 ms 6740 KB Output isn't correct
3 Halted 0 ms 0 KB -