Submission #220391

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
220391	2020-04-07T19:35:30 Z	Andrei_Cotor	Capital City (JOI20_capital_city)	C++11	100 / 100	812 ms	35560 KB

capital_city

#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((int)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[other])
			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;
}

Subtask #1
1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9728 KB	Output is correct
2	Correct	10 ms	9728 KB	Output is correct
3	Correct	10 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	12 ms	9856 KB	Output is correct
9	Correct	9 ms	9728 KB	Output is correct
10	Correct	10 ms	9728 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9728 KB	Output is correct
2	Correct	10 ms	9728 KB	Output is correct
3	Correct	10 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	12 ms	9856 KB	Output is correct
9	Correct	9 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	12 ms	9856 KB	Output is correct
13	Correct	12 ms	9856 KB	Output is correct
14	Correct	12 ms	9856 KB	Output is correct
15	Correct	12 ms	9984 KB	Output is correct
16	Correct	12 ms	9984 KB	Output is correct
17	Correct	11 ms	9984 KB	Output is correct
18	Correct	11 ms	9984 KB	Output is correct
19	Correct	12 ms	9984 KB	Output is correct
20	Correct	12 ms	9984 KB	Output is correct
21	Correct	11 ms	9984 KB	Output is correct
22	Correct	13 ms	9984 KB	Output is correct
23	Correct	12 ms	9984 KB	Output is correct
24	Correct	12 ms	9984 KB	Output is correct
25	Correct	12 ms	9984 KB	Output is correct
26	Correct	12 ms	9984 KB	Output is correct
27	Correct	12 ms	9984 KB	Output is correct
28	Correct	13 ms	9984 KB	Output is correct
29	Correct	14 ms	9984 KB	Output is correct
30	Correct	12 ms	9984 KB	Output is correct

Subtask #3
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	758 ms	35052 KB	Output is correct
2	Correct	267 ms	35560 KB	Output is correct
3	Correct	776 ms	34840 KB	Output is correct
4	Correct	267 ms	35436 KB	Output is correct
5	Correct	772 ms	32492 KB	Output is correct
6	Correct	264 ms	35432 KB	Output is correct
7	Correct	733 ms	32872 KB	Output is correct
8	Correct	273 ms	35356 KB	Output is correct
9	Correct	780 ms	30960 KB	Output is correct
10	Correct	781 ms	29032 KB	Output is correct
11	Correct	801 ms	31476 KB	Output is correct
12	Correct	799 ms	33516 KB	Output is correct
13	Correct	798 ms	28780 KB	Output is correct
14	Correct	787 ms	33896 KB	Output is correct
15	Correct	809 ms	33384 KB	Output is correct
16	Correct	791 ms	29548 KB	Output is correct
17	Correct	800 ms	29804 KB	Output is correct
18	Correct	796 ms	30060 KB	Output is correct
19	Correct	793 ms	32488 KB	Output is correct
20	Correct	797 ms	34288 KB	Output is correct
21	Correct	10 ms	9728 KB	Output is correct

Subtask #4
59.0 / 59.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9728 KB	Output is correct
2	Correct	10 ms	9728 KB	Output is correct
3	Correct	10 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	12 ms	9856 KB	Output is correct
9	Correct	9 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	12 ms	9856 KB	Output is correct
13	Correct	12 ms	9856 KB	Output is correct
14	Correct	12 ms	9856 KB	Output is correct
15	Correct	12 ms	9984 KB	Output is correct
16	Correct	12 ms	9984 KB	Output is correct
17	Correct	11 ms	9984 KB	Output is correct
18	Correct	11 ms	9984 KB	Output is correct
19	Correct	12 ms	9984 KB	Output is correct
20	Correct	12 ms	9984 KB	Output is correct
21	Correct	11 ms	9984 KB	Output is correct
22	Correct	13 ms	9984 KB	Output is correct
23	Correct	12 ms	9984 KB	Output is correct
24	Correct	12 ms	9984 KB	Output is correct
25	Correct	12 ms	9984 KB	Output is correct
26	Correct	12 ms	9984 KB	Output is correct
27	Correct	12 ms	9984 KB	Output is correct
28	Correct	13 ms	9984 KB	Output is correct
29	Correct	14 ms	9984 KB	Output is correct
30	Correct	12 ms	9984 KB	Output is correct
31	Correct	758 ms	35052 KB	Output is correct
32	Correct	267 ms	35560 KB	Output is correct
33	Correct	776 ms	34840 KB	Output is correct
34	Correct	267 ms	35436 KB	Output is correct
35	Correct	772 ms	32492 KB	Output is correct
36	Correct	264 ms	35432 KB	Output is correct
37	Correct	733 ms	32872 KB	Output is correct
38	Correct	273 ms	35356 KB	Output is correct
39	Correct	780 ms	30960 KB	Output is correct
40	Correct	781 ms	29032 KB	Output is correct
41	Correct	801 ms	31476 KB	Output is correct
42	Correct	799 ms	33516 KB	Output is correct
43	Correct	798 ms	28780 KB	Output is correct
44	Correct	787 ms	33896 KB	Output is correct
45	Correct	809 ms	33384 KB	Output is correct
46	Correct	791 ms	29548 KB	Output is correct
47	Correct	800 ms	29804 KB	Output is correct
48	Correct	796 ms	30060 KB	Output is correct
49	Correct	793 ms	32488 KB	Output is correct
50	Correct	797 ms	34288 KB	Output is correct
51	Correct	10 ms	9728 KB	Output is correct
52	Correct	476 ms	21736 KB	Output is correct
53	Correct	539 ms	21740 KB	Output is correct
54	Correct	510 ms	21740 KB	Output is correct
55	Correct	528 ms	21740 KB	Output is correct
56	Correct	544 ms	21740 KB	Output is correct
57	Correct	512 ms	21740 KB	Output is correct
58	Correct	557 ms	24428 KB	Output is correct
59	Correct	545 ms	24680 KB	Output is correct
60	Correct	688 ms	24300 KB	Output is correct
61	Correct	722 ms	24044 KB	Output is correct
62	Correct	271 ms	35436 KB	Output is correct
63	Correct	278 ms	35436 KB	Output is correct
64	Correct	282 ms	35432 KB	Output is correct
65	Correct	270 ms	35432 KB	Output is correct
66	Correct	457 ms	28780 KB	Output is correct
67	Correct	398 ms	28652 KB	Output is correct
68	Correct	413 ms	28780 KB	Output is correct
69	Correct	419 ms	28780 KB	Output is correct
70	Correct	428 ms	28968 KB	Output is correct
71	Correct	402 ms	30188 KB	Output is correct
72	Correct	426 ms	32108 KB	Output is correct
73	Correct	418 ms	31508 KB	Output is correct
74	Correct	415 ms	32364 KB	Output is correct
75	Correct	423 ms	32236 KB	Output is correct
76	Correct	609 ms	31080 KB	Output is correct
77	Correct	593 ms	29548 KB	Output is correct
78	Correct	801 ms	33384 KB	Output is correct
79	Correct	787 ms	31852 KB	Output is correct
80	Correct	812 ms	34792 KB	Output is correct
81	Correct	782 ms	31208 KB	Output is correct
82	Correct	788 ms	31852 KB	Output is correct
83	Correct	784 ms	28656 KB	Output is correct
84	Correct	799 ms	33388 KB	Output is correct
85	Correct	804 ms	32108 KB	Output is correct
86	Correct	784 ms	28136 KB	Output is correct
87	Correct	796 ms	29672 KB	Output is correct
88	Correct	673 ms	30444 KB	Output is correct
89	Correct	669 ms	27372 KB	Output is correct
90	Correct	656 ms	27240 KB	Output is correct
91	Correct	684 ms	29280 KB	Output is correct
92	Correct	691 ms	27884 KB	Output is correct
93	Correct	683 ms	27924 KB	Output is correct
94	Correct	652 ms	27372 KB	Output is correct
95	Correct	670 ms	28524 KB	Output is correct
96	Correct	678 ms	27372 KB	Output is correct
97	Correct	684 ms	29032 KB	Output is correct

Submission #220391

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 10.0 / 10.0

Subtask #3 30.0 / 30.0

Subtask #4 59.0 / 59.0

Subtask #1
1.0 / 1.0

Subtask #2
10.0 / 10.0

Subtask #3
30.0 / 30.0

Subtask #4
59.0 / 59.0