Submission #261897

#	Time	Username	Problem	Language	Result	Execution time	Memory
261897		patrikpavic2	Mergers (JOI19_mergers)	C++17	0 / 100	115 ms	32496 KiB

mergers

#include <cstdio>
#include <vector>

#define PB push_back

using namespace std;

const int N = 5e5 + 500;

vector < int > v[N];
vector < int > koji[N];

int A[N], kol[N], siz[N], sol, bio[N], bla, n;

int dfs(int x, int lst){
	koji[x].PB(A[x]); siz[x] = 1;
	int dolje = 0;
	for(int y : v[x]){ 
		if(y == lst) continue;
		dolje += dfs(y, x); siz[x] += siz[y];
		if(koji[y].size() > koji[x].size())
			swap(koji[x], koji[y]);
		for(int k : koji[y])
			koji[x].PB(k);
	}
	int ja = 0;
	for(int k : koji[x])
		if(!bio[k])
			bio[k] = 1, ja += kol[k];
	for(int k : koji[x])
		bio[k] = 0;
	if(ja == siz[x]){
		sol += (dolje - (x != lst) + 1) / 2;
		dolje = 1;
	}
	return dolje;
}

int main(){
	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", A + i), kol[A[i]]++;
	dfs(1, 1);
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &bla);
  ~~~~~^~~~~~~~~~~~~~~~~~
mergers.cpp:42: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);
             ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:46:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A + i), kol[A[i]]++;
   ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30