Submission #1178853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178853		irmuun	Mergers (JOI19_mergers)	C++20	100 / 100	1360 ms	150688 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll N=5e5+5;

ll n,k;
vector<ll>g[N];
ll s[N],par[N],cnt[N],col[N],sub[N],ex[N];
bool flag[N];

void dfs(ll x,ll p){
    par[x]=p;
    sub[x]=1;
    for(ll y:g[x]){
        if(y!=p){
            dfs(y,x);
            sub[x]+=sub[y];
        }
    }
}
set<ll>solve(ll x){
    set<ll>colors;
    vector<set<ll>>v;
    ll j=-1,mx=0;
    for(ll y:g[x]){
        if(y!=par[x]){
            v.pb(solve(y));
            if(v.back().size()>mx){
                mx=v.back().size();
                j=v.size()-1;
                ex[x]=ex[y];
            }
        }
    }
    v.pb({s[x]});
    if(j>-1){
        swap(colors,v[j]);
    }
    for(ll i=0;i<v.size();i++){
        if(i!=j){
            for(ll c:v[i]){
                if(colors.count(c)==0){
                    colors.insert(c);
                    ex[x]+=cnt[c];
                }
            }
        }
    }
    if(ex[x]==sub[x]){
        flag[x]=true;
    }
    return colors;
}

ll go(){
    queue<ll>r;//roots
    r.push(1);
    ll cur=0;
    while(!r.empty()){
        ll x=r.front();
        r.pop();
        cur++;
        queue<ll>q;
        q.push(x);
        while(!q.empty()){
            ll i=q.front();
            q.pop();
            col[i]=cur;
            for(ll j:g[i]){
                if(j==par[i]) continue;
                if(flag[j]){
                    r.push(j);
                }
                else{
                    q.push(j);
                }
            }
        }
    }
    for(ll i=1;i<=n;i++){
        g[i].clear();
    }
    for(ll i=2;i<=n;i++){
        if(flag[i]){
            g[col[i]].pb(col[par[i]]);
            g[col[par[i]]].pb(col[i]);
        }
    }
    ll leaf=0;
    for(ll i=1;i<=cur;i++){
        if(g[i].size()==1){
            leaf++;
        }
    }
    return leaf;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>k;
    for(ll i=1;i<n;i++){
        ll a,b;
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }
    for(ll i=1;i<=n;i++){
        cin>>s[i];
        cnt[s[i]]++;
    }
    dfs(1,1);
    fill(flag,flag+N+1,false);
    solve(1);
    ll leaf=go();
    cout<<(leaf+1)/2;
}

Compilation message (stderr)

In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from mergers.cpp:1:
In function 'constexpr typename __gnu_cxx::__enable_if<std::__is_scalar<_Tp>::__value, void>::__type std::__fill_a1(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = bool*; _Tp = bool]',
    inlined from 'constexpr void std::__fill_a(_FIte, _FIte, const _Tp&) [with _FIte = bool*; _Tp = bool]' at /usr/include/c++/11/bits/stl_algobase.h:969:21,
    inlined from 'constexpr void std::fill(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = bool*; _Tp = bool]' at /usr/include/c++/11/bits/stl_algobase.h:999:20,
    inlined from 'int main()' at mergers.cpp:120:9:
/usr/include/c++/11/bits/stl_algobase.h:924:18: warning: 'void* __builtin_memset(void*, int, long unsigned int)' writing 500006 bytes into a region of size 500005 overflows the destination [-Wstringop-overflow=]
  924 |         *__first = __tmp;
      |         ~~~~~~~~~^~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:17:6: note: destination object 'flag' of size 500005
   17 | bool flag[N];
      |      ^~~~

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