Submission #1184617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184617		nguyn	Mergers (JOI19_mergers)	C++20	100 / 100	296 ms	83796 KiB

mergers

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

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 5e5 + 5;

struct DSU {
	int n;
	vector<int> lab;

	DSU (int n) : n(n) {
		lab.assign(n + 3, -1);
	}

	int find(int u) {
		return lab[u] < 0 ? u : lab[u] = find(lab[u]); 
	}

	void join(int u, int v) {
		if ((u = find(u)) == (v = find(v))) return; 
		// if (lab[u] > lab[v]) swap(u, v);
		lab[u] += lab[v]; 
		lab[v] = u; 
	}
};

int n, s[N], k;
vector<int> g[N];
vector<int> grp[N];
int par[N], h[N], deg[N];

void pre_dfs(int u, int p) {
	for (int v : g[u]) {
		if (v == p) continue; 
		par[v] = u; 
		h[v] = h[u] + 1;
		pre_dfs(v, u);
	}
}

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
    	int u, v;
    	cin >> u >> v;
    	g[u].pb(v);
    	g[v].pb(u);
    }
    for (int i = 1; i <= n; i++) {
    	cin >> s[i];
    	grp[s[i]].pb(i);
    }
    par[1] = 1; 
    pre_dfs(1, 0);
    DSU dsu(n); 
    for (int i = 1; i <= k; i++) {
    	if (grp[i].empty()) continue; 
    	for (int j = 1; j < grp[i].size(); j++) {
    		int u = grp[i][j]; 
    		int v = grp[i][j - 1];
    		u = dsu.find(u); v = dsu.find(v); 
    		while(u != v) {
    			if (h[u] > h[v]) swap(u, v); 
    			dsu.join(u, v);
    			v = dsu.find(par[v]);
    			u = dsu.find(u); 
    		}
    	}
    }
    for (int i = 1; i <= n; i++) {
    	int u = dsu.find(i); 
    	for (int j : g[i]) {
    		int v = dsu.find(j);
    		if (u != v) deg[u]++; 
    	}
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
    	res += (deg[i] == 1);
    }
    cout << (res + 1) / 2;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mergers.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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