Submission #1104981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104981		hiensumi	Capital City (JOI20_capital_city)	C++14	100 / 100	484 ms	74940 KiB

capital_city

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;

typedef pair<int,int>P;
#define SZ 500005
#define CNUM 500005
#define INF 1000000000

int n,k,col[SZ];
vector<int>edge[SZ];
vector<int>vertex[CNUM];
bool rem[SZ];
int sub_size[SZ];
int ans = 1000000000;
bool check_col[CNUM];
int up[SZ];
vector<int>cur_vertex, cur_list[CNUM];

int make(int v,int u){
	int cnt = 1;
	up[v] = u;
	check_col[col[v]] = 0;
	cur_vertex.push_back(v);
	cur_list[col[v]].clear();
	for(int i=0;i<edge[v].size();i++){
		int to = edge[v][i];
		if(rem[to] || to == u) continue;
		cnt += make(to,v);
	}
	return sub_size[v] = cnt;
}
P search(int v,int u,int cur_size){
	P ret = P(1000000000,-1);
	int sum=1,mx=0;
	for(int i=0;i<edge[v].size();i++){
		int to = edge[v][i];
		if(rem[to] || to == u) continue;
		ret = min(ret,search(to,v,cur_size));
		mx = max(mx,sub_size[to]);
		sum += sub_size[to];
	}
	mx = max(mx,cur_size-sum);
	ret = min(ret,P(mx,v));
	return ret;
}
void sol(int v){
	make(v,-1);
	cur_vertex.clear();
	int cent = search(v,-1,sub_size[v]).second;
	make(cent,-1);
	rem[cent] = true;
	int sz = cur_vertex.size();
	for(int i=0;i<sz;i++) cur_list[col[cur_vertex[i]]].push_back(cur_vertex[i]);
	queue<int>que;
	que.push(col[cent]);
	check_col[col[cent]] = 1;
	int use = 0;
	while(!que.empty()){
		int c = que.front(); que.pop();
		use++;
		if(cur_list[c].size() != vertex[c].size()){
			use = INF;
			break;
		}
		for(int i=0;i<cur_list[c].size();i++){
			int look = cur_list[c][i];
			if(up[look] == -1) continue;
			int nw = col[up[look]];
			if(!check_col[nw]){
				que.push(nw);
				check_col[nw] = 1;
			}
		}
	}
	ans = min(ans,use);
	for(int i=0;i<edge[cent].size();i++){
		if(!rem[edge[cent][i]]) sol(edge[cent][i]);
	}
	rem[cent] = false;
}
int main(){
	scanf("%d %d",&n,&k);
	for(int i=1;i<n;i++){
		int a,b; scanf("%d%d",&a,&b);
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&col[i]);
		vertex[col[i]].push_back(i);
	}
	sol(1);
	assert(ans <= n);
	printf("%d\n",ans-1);
	return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'int make(int, int)':
capital_city.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i=0;i<edge[v].size();i++){
      |              ~^~~~~~~~~~~~~~~
capital_city.cpp: In function 'P search(int, int, int)':
capital_city.cpp:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i=0;i<edge[v].size();i++){
      |              ~^~~~~~~~~~~~~~~
capital_city.cpp: In function 'void sol(int)':
capital_city.cpp:72:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i=0;i<cur_list[c].size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~
capital_city.cpp:83:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(int i=0;i<edge[cent].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%d %d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~
capital_city.cpp:91:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   int a,b; scanf("%d%d",&a,&b);
      |            ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d",&col[i]);
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59