Submission #716266

#	Time	Username	Problem	Language	Result	Execution time	Memory
716266		Ahmed57	Mergers (JOI19_mergers)	C++14	0 / 100	170 ms	90396 KiB

mergers

#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 arr[200001] , cnt[200001];
bool mark[200001];
pair<int,map<int,int>> dfs(int i,int pr){
    map<int,int> mp;
    pair<int,map<int,int>> p1;
    int bad = 0;
    mp[arr[i]]++;
    if(cnt[arr[i]]!=1)bad++;
    for(auto j:g[i]){
        if(j!=pr){
            p1 = dfs(j,i);
            bad+=p1.first;
            if(p1.second.size()>mp.size())swap(mp,p1.second);
            for(auto k:p1.second){
                if(mp[k.first]!=0)bad--;
                mp[k.first]+=k.second;
                if(mp[k.first]==cnt[k.first]&&k.second!=cnt[k.first])bad--;
            }
        }
    }
    if(bad==0){
        mark[i] = 1;
    }
    return {bad,mp};
}
int calc(int i,int pr){
    int sum = 0;
    for(auto j:g[i]){
        if(j==pr)continue;
        sum+=calc(j,i);
    }
    if(mark[i]){
        if(sum)return sum;
        else return 1;
    }else return sum;
}
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);
        arr[i] = v;
        cnt[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++;
    pair<int,map<int,int>>p1 = dfs(1,0);
    mark[1] = 0;
    int ans = calc(1,0);
    if((ans+1)/2<(cnt+1)/2)assert(0);
    printf("%d\n", (cnt+1) / 2);
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int j = 1; j < col[i].size(); ++j) {
      |                        ~~^~~~~~~~~~~~~~~
mergers.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%d", &v);
      |         ~~~~~^~~~~~~~~~

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