Submission #105454

#	Time	Username	Problem	Language	Result	Execution time	Memory
105454		reality	Mergers (JOI19_mergers)	C++17	100 / 100	1890 ms	201984 KiB

mergers

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
#define pp pair < pair < int , vi > , map < int , int > >
const int N = 1e6 + 5;
int cnt[N];
void comb(pp &a,pp & b) {
    if (a.se.size() < b.se.size())
        swap(a,b);
    if (a.fi.se.size() < b.fi.se.size())
        swap(a.fi.se,b.fi.se);
    for (auto it : b.fi.se)
        a.fi.se.pb(it);
    a.fi.fi += b.fi.fi;
    for (auto it : b.se) {
        a.se[it.fi] += it.se;
        a.fi.fi += a.se[it.fi] == cnt[it.fi] && it.se < cnt[it.fi];
    }
    b.fi.fi = 0;
    b.fi.se.clear();
    b.se.clear();
}
vi g[N];
int v[N];
int flag[N];
int deg[N];
pp M[N];
int R = 0;
void dfs(int node,int prev) {
    M[node].fi.fi = cnt[v[node]] == 1;
    M[node].fi.se.pb(node);
    M[node].se[v[node]] = 1;
    for (auto it : g[node]) {
        if (it == prev)
            continue;
        dfs(it,node);
        comb(M[node],M[it]);
    }
    if (M[node].fi.fi == M[node].se.size()) {
        ++R;
        for (auto it : M[node].fi.se)
            flag[it] = R;
        M[node].fi.fi = 0;
        M[node].fi.se.clear();
        M[node].se.clear();
    }
}
int main(void) {
    int n,k;
    cin.tie(0);
    ios_base :: sync_with_stdio(0);
    cin>>n>>k;
    vii e;
    for (int i = 1;i < n;++i) {
        int a,b;
        cin>>a>>b;
        e.pb(mp(a,b));
        g[a].pb(b);
        g[b].pb(a);
    }
    for (int i = 1;i <= n;++i) {
        cin>>v[i];
        cnt[v[i]] += 1;
    }
    dfs(1,0);
    if (R == 1) {
        puts("0");
        return 0;
    }
    if (R == 2) {
        puts("1");
        return 0;
    }
    int ans = 0;
    for (auto it : e)
        if (flag[it.fi] != flag[it.se])
            ++deg[flag[it.fi]],++deg[flag[it.se]];
    for (int i = 1;i <= R;++i)
        ans += deg[i] == 1;
    cout << ((ans + 1) / 2) << '\n';
    return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'void dfs(int, int)':
mergers.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (M[node].fi.fi == M[node].se.size()) {
         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

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