Submission #210364

#	Time	Username	Problem	Language	Result	Execution time	Memory
210364		arman_ferdous	Mergers (JOI19_mergers)	C++14	100 / 100	815 ms	85596 KiB

mergers

// taken from https://github.com/win11905/submission/blob/master/JOISC/19/mergers.cpp
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int N = 5e5+5;

int n, k;
vector<int> g[N];
vector<pii> E;
int dep[N], dsu[N], deg[N], par[N];
vector<int> col[N];

int find(int u) { return dsu[u] = dsu[u] == u ? u : find(dsu[u]); }

void init_dep(int u, int p) {
    dep[u] = dep[p] + 1, par[u] = p;
    for(int v : g[u]) if(v != p) init_dep(v, u);
}

int main() {
    iota(dsu, dsu+N, 0);
    scanf("%d %d", &n, &k);
    for(int i = 1, u, v; i < n; ++i) {
        scanf("%d %d", &u, &v);
        g[u].emplace_back(v), g[v].emplace_back(u);
        E.emplace_back(u, v);
    }
    for(int i = 1, v; i <= n; ++i) {
        scanf("%d", &v);
        col[v].emplace_back(i);
    }
    init_dep(1, 0);
    for(int i = 1; i <= k; ++i) if(col[i].size() > 1) {
        for(int j = 1; j < col[i].size(); ++j) {
            int a = find(col[i][j-1]), b = find(col[i][j]);
            while(a != b) {
                if(dep[a] < dep[b]) swap(a, b);
                dsu[a] = find(par[a]);
                a = dsu[a];
            }
        } 
    }
    for(auto x : E) {
        int a = find(x.x), b = find(x.y);
        if(a != b) deg[a]++, deg[b]++;
    }
    int cnt = 0;
    for(int i = 1; i <= n; ++i) if(deg[i] == 1) cnt++;
    printf("%d\n", (cnt+1) / 2);
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:37:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 1; j < col[i].size(); ++j) {
                        ~~^~~~~~~~~~~~~~~
mergers.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &v);
         ~~~~~^~~~~~~~~~

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