oj.uz

Submission #378209

# Submission time Handle Problem Language Result Execution time Memory
378209 2021-03-16T08:26:19 Z iris2617 Capital City (JOI20_capital_city) C++14
1 / 100
 793 ms 47084 KB 
#include<bits/stdc++.h>
#define int long long
#define matsuri pair<int,int>
#define iris 1000000007
using namespace std;

vector<int> G[200010],aoi[200010];
int arr[200010];
int sz[200010],sum,x,pr[200010];
int v[200010],vv[200010],color[200010],tt;
queue<int> q;
bitset<200010> del;

void dfs(int a)
{
	v[a]=tt;
	sz[a]=1;
	for(int b:G[a])
	{
		if(v[b]==tt || del[b])
			continue;
		dfs(b);
		sz[a]+=sz[b];
	}
}

void dc(int a,int f)
{
	int ouo=0;
	for(int b:G[a])
	{
		if(b==f || del[b])
			continue;
		dc(b,a);
		ouo=max(ouo, sz[b]);
	}
	ouo=max(ouo, sum-sz[a]);
	if(ouo<=sum/2)
		x=a;
}

void dfs2(int a,int f)
{
	pr[a]=f;
	for(int b:G[a])
	{
		if(b==f || del[b])
			continue;
		dfs2(b,a);
	}
}

int sana(int a)
{
	tt++;
	dfs(a);
	sum=sz[a];
	dc(a,0);
	dfs2(x,0);
	
	int ans=0;
	bool flag=0;
	del[x]=1;
	vv[x]=tt;
	color[arr[x]]=1;
	q.push(arr[x]);
	while(!q.empty())
	{
		int k=q.front();
		q.pop();
		for(int a:aoi[k])
		{
			if(v[a]!=tt)
			{
				flag=1;
				break;
			}
			while(vv[a]!=tt)
			{
				vv[a]=tt;
				if(color[arr[a]]!=tt)
				{
					color[arr[a]]=tt;
					q.push(arr[a]);
					ans++;
				}
				a=pr[a];
			}
		}
	}
	if(flag)
		ans=1e9;
//	cout<<' '<<x<<' '<<ans<<'\n';
	
	for(int b:G[x])
	{
		if(del[b])
			continue;
		ans=min(ans, sana(b));
	}
	return ans;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,k,a,b,i;
	
	cin>>n>>k;
	for(i=1;i<n;i++)
	{
		cin>>a>>b;
		G[a].emplace_back(b);
		G[b].emplace_back(a);
	}
	for(i=1;i<=n;i++)
	{
		cin>>a;
		arr[i]=a;
		aoi[a].emplace_back(i);
	}
	cout<<sana(1)<<'\n';
	
	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9964 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 7 ms 9856 KB Output is correct
4 Correct 7 ms 9856 KB Output is correct
5 Correct 7 ms 9836 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 7 ms 9836 KB Output is correct
8 Correct 7 ms 9836 KB Output is correct
9 Correct 7 ms 9848 KB Output is correct
10 Correct 7 ms 9836 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9964 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 7 ms 9856 KB Output is correct
4 Correct 7 ms 9856 KB Output is correct
5 Correct 7 ms 9836 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 7 ms 9836 KB Output is correct
8 Correct 7 ms 9836 KB Output is correct
9 Correct 7 ms 9848 KB Output is correct
10 Correct 7 ms 9836 KB Output is correct
11 Correct 11 ms 9964 KB Output is correct
12 Correct 11 ms 9964 KB Output is correct
13 Correct 11 ms 9964 KB Output is correct
14 Correct 9 ms 9964 KB Output is correct
15 Incorrect 9 ms 10092 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 46700 KB Output is correct
2 Correct 230 ms 47084 KB Output is correct
3 Correct 793 ms 46444 KB Output is correct
4 Correct 227 ms 47084 KB Output is correct
5 Incorrect 783 ms 43500 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9964 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 7 ms 9856 KB Output is correct
4 Correct 7 ms 9856 KB Output is correct
5 Correct 7 ms 9836 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 7 ms 9836 KB Output is correct
8 Correct 7 ms 9836 KB Output is correct
9 Correct 7 ms 9848 KB Output is correct
10 Correct 7 ms 9836 KB Output is correct
11 Correct 11 ms 9964 KB Output is correct
12 Correct 11 ms 9964 KB Output is correct
13 Correct 11 ms 9964 KB Output is correct
14 Correct 9 ms 9964 KB Output is correct
15 Incorrect 9 ms 10092 KB Output isn't correct
16 Halted 0 ms 0 KB -