oj.uz

Submission #220389

# Submission time Handle Problem Language Result Execution time Memory
220389 2020-04-07T19:30:19 Z Andrei_Cotor Capital City (JOI20_capital_city) C++11
1 / 100
 240 ms 35284 KB 
#include<iostream>
#include<vector>
#include<deque>
#include<algorithm>

using namespace std;

vector<int> Adj[200005];
vector<int> Towns[200005];
vector<int> RelevantCities;
bool Centroid[200005];
bool Merged[200005];
int Sz[200005],P[200005];
int NrCity[200005],City[200005];
int rez;

void getsz(int nod, int p)
{
	Sz[nod]=1;
	Towns[City[nod]].push_back(nod);
	RelevantCities.push_back(City[nod]);

	for(auto other:Adj[nod])
	{
		if(other==p || Centroid[other])
			continue;

		getsz(other,nod);

		Sz[nod]+=Sz[other];
	}
}

void getParents(int nod, int p)
{
	P[nod]=p;
	for(auto other:Adj[nod])
	{
		if(other==p || Centroid[other])
			continue;

		getParents(other,nod);
	}
}

int getCentroid(int nod, int p, int sztot)
{
	int nxt=-1;
	for(auto other:Adj[nod])
	{
		if(other==p || Centroid[other])
			continue;

		if(sztot/2<Sz[other])
			nxt=other;
	}

	if(nxt!=-1)
		return getCentroid(nxt,nod,sztot);
	return nod;
}

void centroidDecomp(int nod)
{
	getsz(nod,0);

	nod=getCentroid(nod,0,Sz[nod]);
	Centroid[nod]=true;

	getParents(nod,0);

	deque<int> Q;
	for(auto town:Towns[City[nod]])
	{
		if(town==nod)
			continue;
		Q.push_back(town);
	}

	Merged[City[nod]]=1;
	while(!Q.empty())
	{
		int town=Q.front();
		Q.pop_front();

		if(!Merged[City[P[town]]])
		{
			Merged[City[P[town]]]=1;
			for(auto other:Towns[City[P[town]]])
				Q.push_back(other);
		}
	}

	int nrmerges=0;
	bool ok=true;
	for(auto city:RelevantCities)
	{
		if(Merged[city])
		{
			if(Towns[city].size()!=NrCity[city])
				ok=false;

			nrmerges++;
			Merged[city]=0;
		}
		Towns[city].clear();
	}
	RelevantCities.clear();

	nrmerges--;
	if(ok)
		rez=min(rez,nrmerges);

	for(auto other:Adj[nod])
	{
		if(!Centroid[nod])
			centroidDecomp(other);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n,k;
	cin>>n>>k;

	for(int i=1; i<n; i++)
	{
		int x,y;
		cin>>x>>y;
		Adj[x].push_back(y);
		Adj[y].push_back(x);
	}

	for(int i=1; i<=n; i++)
	{
		cin>>City[i];
		NrCity[City[i]]++;
	}

	rez=1000000000;
	centroidDecomp(1);

	cout<<rez<<"\n";
	return 0;
}

Compilation message

capital_city.cpp: In function 'void centroidDecomp(int)':
capital_city.cpp:100:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(Towns[city].size()!=NrCity[city])
       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 9 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 10 ms 9728 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 34796 KB Output is correct
2 Correct 126 ms 35284 KB Output is correct
3 Correct 240 ms 34540 KB Output is correct
4 Correct 124 ms 35180 KB Output is correct
5 Incorrect 210 ms 32108 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

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