Submission #262023

#	Time	Username	Problem	Language	Result	Execution time	Memory
262023		patrikpavic2	Mergers (JOI19_mergers)	C++17	100 / 100	857 ms	97400 KiB

mergers

#include <cstdio>
#include <cstdlib>
#include <vector>

#define PB push_back

using namespace std;

const int N = 5e5 + 500;

vector < int > v[N], v2[N];

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

inline int pr(int x){
	if(x == par[x]) return x;
	return par[x] = pr(par[x]);
}

inline void mrg(int x, int y){
	par[pr(x)] = pr(y);
}

int dfs(int x, int lst){
	int ret = hsh[x];
	for(int y : v[x]){ 
		if(y == lst) continue;
		ret += dfs(y, x);
	}
	//printf("x = %d ret = %d\n", x, ret);
	if(ret != 0)
		mrg(x, lst);
	return ret;
}

int f(int x, int lst){
	if((int)v2[x].size() == 1) return 1;
	if(x == lst){
		int dos = 0;
		for(int y : v2[x]){
			int nov = f(y, x);
			if(dos < nov) {nov ^= dos, dos ^= nov, nov ^= dos;}
			sol += nov, dos -= nov;
		}
		sol += dos;
		return 0;
	}
	int ret = 0;
	for(int y : v2[x])
		if(y != lst)
			ret += f(y, x);
	if(ret % 1){
		sol += ret / 2; ret = 1;
	}
	else{
		sol += (ret - 2) / 2;
		ret = 2;
	}
	return ret;
}

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);
		zad[A[i]] = i; par[i] = i;
	}
	for(int i = 1;i <= n;i++){
		if(zad[A[i]] != i)
			hsh[i] = rand() * rand();
		else
			hsh[i] = -kol[A[i]];
		kol[A[i]] += hsh[i];
	}
	dfs(1, 1);
	for(int i = 1;i <= n;i++){
		for(int x : v[i])
			if(pr(x) != pr(i))
				v2[pr(i)].PB(pr(x));
	}
	if((int)v2[pr(1)].size() == 0){
		printf("0\n");
		return 0;	
	}
	
	int list = 0;
	for(int i = 1;i <= n;i++)
		if(v2[i].size() == 1)
			list++;
	printf("%d\n", (list + 1) / 2);	
	return 0;
	
	int root = -1;
	for(int i = 1;i <= n;i++)
		if(pr(i) == i && (int)v2[i].size() != 1)
			root = i;
	if(root == -1){
		printf("1\n");
		return 0;
	}
	f(root, root);
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:64: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:66: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:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A + i);
   ~~~~~^~~~~~~~~~~~~

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