Submission #221460

#	Time	Username	Problem	Language	Result	Execution time	Memory
221460		patrikpavic2	Capital City (JOI20_capital_city)	C++17	100 / 100	1273 ms	37216 KiB

capital_city

#include <cstdio>
#include <vector>
#include <queue>

#define PB push_back

using namespace std;

const int N = 2e5 + 500;

int sub[N], uzeo[N], C[N], cnt[N], zabr[N], par[N], centr[N], kol[N], uk[N];
int fin = N, n;
vector < int > moji, koji[N], v[N];

void dfs(int x, int lst){
	sub[x] = 1; moji.PB(x);
	par[x] = lst;
	for(int y : v[x]){
		if(centr[y] || lst == y) continue;
		dfs(y, x); sub[x] += sub[y]; 
	}
}

int nadi(int x){
	dfs(x, x);
	int nn = (int)moji.size();
	int dos = x;
	for(int y : moji){
		if(2 * sub[y] >= nn && sub[y] < sub[dos])
			dos = y;
	}
	moji.clear();
	return dos;
}

void rijesi(int x){
	dfs(x, x);
	queue < int > q; q.push(x);
	for(int y : moji) koji[C[y]].PB(y);
	for(;!q.empty();q.pop()){
		if(uzeo[q.front()])
			continue;
		int cur = q.front();
		while(!uzeo[cur]){
			if(!kol[C[cur]]){
				for(int y : koji[C[cur]])
					q.push(y);
			}
			uzeo[cur] = 1; kol[C[cur]]++;
			cur = par[cur];	
		}
	}
	for(int y : moji) koji[C[y]].clear(), uzeo[y] = 0;
	int mogu = 1, ret = 0;
	for(int y : moji){
		if(!kol[C[y]]) continue;
		if(kol[C[y]] < uk[C[y]]){
			mogu = 0; kol[C[y]] = 0;
		}
		kol[C[y]] = 0, ret++;
	}
	if(mogu)
		fin = min(fin, ret);
	moji.clear();
}

void glupost(int x){
	int cen = nadi(x);
	rijesi(cen);
	centr[cen] = 1;
	for(int y : v[cen]){
		if(!centr[y])
			glupost(y);
	}
}

int main(){
	int bla; scanf("%d%d", &n, &bla);
	for(int i = 1;i < n;i++){
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y), v[y].PB(x);
	}
	for(int i = 1;i <= n;i++)
		scanf("%d", C + i), uk[C[i]]++;
	glupost(1);
	printf("%d\n", fin - 1);
	return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:78:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int bla; scanf("%d%d", &n, &bla);
           ~~~~~^~~~~~~~~~~~~~~~~~
capital_city.cpp:80:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:84:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", C + i), uk[C[i]]++;
   ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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