제출 #391058

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391058		parsabahrami	Mergers (JOI19_mergers)	C++17	100 / 100	1030 ms	108300 KiB

mergers

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 5e5 + 10;
int S[N], ps[N], St[N], big[N], C[N], P[N], H[N], M[N], HD[N], A[N], n, k, tim, ret = 0;
vector<int> adj[N], vec[N];

void szDFS(int v, int p = -1) {
	S[v] = 1;
	for (int u : adj[v]) {
		if (u != p) {
			H[u] = H[v] + 1, P[u] = v;
			szDFS(u, v); S[v] += S[u];
			if (S[u] > S[big[v]]) big[v] = u;
		}
	}
}
 
void HLD(int v, int p = -1) {
	if (p == -1) HD[v] = v;
	St[v] = tim++;
	if (big[v]) HD[big[v]] = HD[v], HLD(big[v], v);
	for (int u : adj[v]) {
		if (u != p && u != big[v]) {
			HD[u] = u, HLD(u, v);
		}
	}
}

int LCA(int u, int v){
    while (HD[u] != HD[v]){
        if (H[HD[u]] > H[HD[v]]) u = P[HD[u]];
        else v = P[HD[v]];
    }
    return H[u] < H[v] ? u : v;
}

void DFS(int v, int p = -1) {
    for (int u : adj[v]) {
        if (u != p) {
            DFS(u, v);
            ps[v] += ps[u], C[v] += C[u];
            if (!ps[u]) M[u] = 1;
        }
    }
    if (~p && !ps[v] && !C[v]) C[v] = 1;
}

void calcDFS(int v, int p = -1, int cnt = 0) {
    int sum = 0, id = 0;
    if (M[v] && !cnt) ret++, cnt = 1;
    for (int u : adj[v]) {
        if (u != p) {
            sum += C[u];
            if (C[u] >= C[id]) id = u;
        }
    }
    if (sum - C[id] + cnt >= C[id]) ret += max(0, (sum - cnt) / 2) + (max(0, (sum - cnt)) & 1);
    else ret += sum - C[id], calcDFS(id, v, cnt + sum - C[id]);
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    for (int i = 1; i <= n; i++) scanf("%d", &A[i]), vec[A[i]].push_back(i);
    szDFS(1); HLD(1);
    for (int i = 1; i <= k; i++) {
        sort(vec[i].begin(), vec[i].end(), [&] (int u, int v) { return St[u] < St[v]; });
        for (int j = 0; j + 1 < SZ(vec[i]); j++) {
            int p = LCA(vec[i][j], vec[i][j + 1]);
            ps[p] -= 2, ps[vec[i][j + 1]]++, ps[vec[i][j]]++;
        }
    }
    DFS(1);
    calcDFS(1);
    printf("%d\n", ret);
    return 0;
}

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

mergers.cpp: In function 'int main()':
mergers.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:74:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |         int u, v; scanf("%d%d", &u, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:78:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |     for (int i = 1; i <= n; i++) scanf("%d", &A[i]), vec[A[i]].push_back(i);
      |                                  ~~~~~^~~~~~~~~~~~~

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