제출 #1307597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307597		nanaseyuzuki	Mergers (JOI19_mergers)	C++20	100 / 100	567 ms	120996 KiB

mergers

#include <bits/stdc++.h>
// Kazusa_Megumi
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;

int n, k, s[mn], up[mn][20], d[mn];
vector <int> a[mn], col[mn];

void dfs(int u, int p){
	for(auto v : a[u]){
		if(v == p) continue;
		up[v][0] = u;
		d[v] = d[u] + 1;
		dfs(v, u);
	}
}

void build(){
	for(int lg = 1; lg < 19; lg++){
		for(int i = 1; i <= n; i++){
			if(up[i][lg - 1] != -1) up[i][lg] = up[up[i][lg - 1]][lg - 1];
		}
	}
}

int lca(int u, int v){
	if(d[u] < d[v]) swap(u, v);
	int kc = d[u] - d[v];
	for(int i = 18; i >= 0; i--){
		if(kc & (1 << i)) u = up[u][i];
	}

	if(u == v) return u;
	for(int i = 18; i >= 0; i--){
		if(up[u][i] != up[v][i] && up[u][i] != -1 && up[v][i] != -1){
			u = up[u][i], v = up[v][i];
		}
	}
	return up[u][0];
}

int par[mn];

void init(){
	for(int i = 1; i <= n; i++) par[i] = i;
}

int find(int u){
	if(u == par[u]) return u;
	return par[u] = find(par[u]);
}

void join(int u, int v){
	// cerr << "Join " << u << ' ' << v << '\n';
	u = find(u), v = find(v);
	if(u == v) return;
	if(d[u] > d[v]) par[u] = v;
	else par[v] = u;
}

void merge(int u, int v){
	// cerr << "Merge " << u << ' ' << v << '\n';
	while(u != v){
		if(d[u] > d[v]){
			join(u, up[u][0]);
			u = find(u);
		}
		else{
			join(v, up[v][0]);
			v = find(v);
		}
	}
}

void solve() {
    cin >> n >> k;
    for(int i = 1; i < n; i++){
    	int u, v; cin >> u >> v;
    	a[u].push_back(v);
    	a[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
    	cin >> s[i];
    	col[s[i]].push_back(i);
    }

    memset(up, -1, sizeof(up));
   	dfs(1, 0); build(); init();

   	for(int i = 1; i <= n; i++){
   		for(auto u : col[i]){
   			merge(u, col[i][0]);
   		}
   	}

   	vector <int> cnt(n + 1);
   	for(int i = 1; i <= n; i++){
   		for(auto j : a[i]){
   			if(find(i) != find(j)) cnt[find(i)] ++;
   		}
   	}
   	int res = 0;
   	for(int i = 1; i <= n; i++) res += (cnt[i] == 1);
   	cout << (res + 1) / 2;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    if (fopen("Kazuki.INP", "r")) {
        freopen("Kazuki.INP", "r", stdin);
        freopen("Kazuki.OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

mergers.cpp:113:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  113 | main() {
      | ^~~~
mergers.cpp: In function 'int main()':
mergers.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen("Kazuki.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
mergers.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen("Kazuki.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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