oj.uz

Submission #378322

# Submission time Handle Problem Language Result Execution time Memory
378322 2021-03-16T13:26:47 Z iris2617 Capital City (JOI20_capital_city) C++14
0 / 100
 1412 ms 34540 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 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++;
	x=a;
	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])
		{
			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;
	
	return ans;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,k,a,b,i,ans=1e9;
	
	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);
	}
	for(i=1;i<=n;i++)
	{
		ans=min(ans, sana(i));
	}
	cout<<ans<<'\n';
	
	return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 6 ms 9720 KB Output is correct
4 Incorrect 6 ms 9728 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 6 ms 9720 KB Output is correct
4 Incorrect 6 ms 9728 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 6 ms 9720 KB Output is correct
4 Incorrect 6 ms 9728 KB Output isn't correct
5 Halted 0 ms 0 KB -