Submission #1178843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178843		irmuun	Mergers (JOI19_mergers)	C++20	34 / 100	3096 ms	24352 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];
bool flag[N];

void dfs(ll x,ll p){
    par[x]=p;
    for(ll y:g[x]){
        if(y!=p){
            dfs(y,x);
        }
    }
}
bool solve(ll i){
    queue<ll>q;
    q.push(i);
    set<ll>st;
    ll sub=0;
    while(!q.empty()){
        ll x=q.front();
        q.pop();
        sub++;
        st.insert(s[x]);
        for(ll y:g[x]){
            if(y!=par[x]){
                q.push(y);
            }
        }
    }
    ll tot=0;
    for(ll c:st){
        tot+=cnt[c];
    }
    if(tot==sub){//seperated
        return true;
    }
    return false;
}

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);
    for(ll i=2;i<=n;i++){
        if(solve(i)){
            flag[i]=true;
        }
    }
    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:110: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: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30