oj.uz

Submission #378255

# Submission time Handle Problem Language Result Execution time Memory
378255 2021-03-16T10:42:01 Z iris2617 Capital City (JOI20_capital_city) C++14
1 / 100
 790 ms 47244 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);
	assert(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 8 ms 9984 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 8 ms 9836 KB Output is correct
4 Correct 8 ms 9836 KB Output is correct
5 Correct 8 ms 9836 KB Output is correct
6 Correct 7 ms 9836 KB Output is correct
7 Correct 7 ms 9856 KB Output is correct
8 Correct 7 ms 9836 KB Output is correct
9 Correct 7 ms 9836 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 8 ms 9984 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 8 ms 9836 KB Output is correct
4 Correct 8 ms 9836 KB Output is correct
5 Correct 8 ms 9836 KB Output is correct
6 Correct 7 ms 9836 KB Output is correct
7 Correct 7 ms 9856 KB Output is correct
8 Correct 7 ms 9836 KB Output is correct
9 Correct 7 ms 9836 KB Output is correct
10 Correct 7 ms 9836 KB Output is correct
11 Correct 9 ms 9964 KB Output is correct
12 Correct 9 ms 9964 KB Output is correct
13 Correct 10 ms 9964 KB Output is correct
14 Correct 9 ms 9964 KB Output is correct
15 Incorrect 10 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 790 ms 46564 KB Output is correct
2 Correct 232 ms 47244 KB Output is correct
3 Correct 789 ms 46316 KB Output is correct
4 Correct 223 ms 47084 KB Output is correct
5 Incorrect 737 ms 43372 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

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