Submission #332888

#	Time	Username	Problem	Language	Result	Execution time	Memory
332888		peuch	Mergers (JOI19_mergers)	C++17	100 / 100	1588 ms	149460 KiB

mergers

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 500010;
const int MAXL = 26;

int n, q;

int prof[MAXN];
int dp[MAXN][MAXL];

int marc[MAXN];

int rep[MAXN], tam[MAXN];
int in[MAXN];

int fol;

vector<int> states[MAXN];
vector<int> ar[MAXN];

void preCalc(int cur, int pai);
int lca(int a, int b);
void calc(int cur, int pai);
void uni(int a, int b);
int find(int a);

int main(){
	scanf("%d %d", &n, &q);
	
	for(int i = 1; i < n; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		ar[a].push_back(b);
		ar[b].push_back(a);
	}
	
	for(int i = 1; i <= n; i++){
		rep[i] = i;
		tam[i] = 1;
		marc[i] = 1;
		int aux;
		scanf("%d", &aux);
		states[aux].push_back(i);
	}
	preCalc(1, 0);
	
	for(int i = 1; i <= q; i++){
		int anc = states[i][0];
		for(int j = 1; j < states[i].size(); j++)
			anc = lca(anc, states[i][j]);
		marc[anc] -= states[i].size();
	}
	calc(1, 0);
	
	for(int i = 2; i <= n; i++){
		if(marc[i] == 0) continue;
		uni(i, dp[i][0]);
	}

	for(int i = 2; i <= n; i++){
		if(marc[i] != 0) continue;
		in[find(i)]++;
		in[find(dp[i][0])]++;
	}
	

	for(int i = 1; i <= n; i++)
		if(in[i] == 1) fol++;
	
	printf("%d\n", (fol + 1) / 2);
}

void preCalc(int cur, int pai){
	for(int k = 1; k < MAXL; k++)
		dp[cur][k] = dp[dp[cur][k - 1]][k - 1];
	for(int i = 0; i < ar[cur].size(); i++){
		int viz = ar[cur][i];
		if(viz == pai) continue;
		prof[viz] = prof[cur] + 1;
		dp[viz][0] = cur;
		preCalc(viz, cur);
	}
}

int lca(int a, int b){
	if(prof[a] < prof[b]) swap(a, b);
	int d = prof[a] - prof[b];
	for(int k = 0; k < MAXL; k++)
		if((1 << k) & d) a = dp[a][k];
	if(a == b) return a;
	for(int k = MAXL - 1; k >= 0; k--)
		if(dp[a][k] != dp[b][k]) a = dp[a][k], b = dp[b][k];
	return dp[a][0];
}

void calc(int cur, int pai){
	for(int i = 0; i < ar[cur].size(); i++){
		int viz = ar[cur][i];
		if(viz == pai) continue;
		calc(viz, cur);
		marc[cur] += marc[viz];
	}
}

void uni(int a, int b){
	a = find(a);
	b = find(b);
	if(a == b) return;
	if(tam[a] > tam[b]) tam[a] += tam[b], rep[b] = a;
	else tam[b] += tam[a], rep[a] = b;
}

int find(int a){
	if(rep[a] == a) return a;
	return rep[a] = find(rep[a]);
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int j = 1; j < states[i].size(); j++)
      |                  ~~^~~~~~~~~~~~~~~~~~
mergers.cpp: In function 'void preCalc(int, int)':
mergers.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i = 0; i < ar[cur].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
mergers.cpp: In function 'void calc(int, int)':
mergers.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for(int i = 0; i < ar[cur].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |   scanf("%d", &aux);
      |   ~~~~~^~~~~~~~~~~~

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