Submission #1046953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046953		isaachew	Mergers (JOI19_mergers)	C++17	100 / 100	501 ms	136360 KiB

mergers

#include <bits/stdc++.h>
/*
 An edge is separable if the states on either side are disjoint
 "Unify" an entire path between edges
 Every city is a unique state -> min number of paths to cover induced tree of separable edges
 Root at "centroid" (vertex that splits leaves into sections of less than half), get leaves -> solved
 STL and look at num. distinct values to see if separable
 */
std::vector<std::vector<int>> edges;
std::vector<int> states;
std::vector<int> stamounts;
std::vector<int> parents;
std::vector<int> separable;
int nleaves=0;
std::map<int,int>* dfs(int cur,int parent=0){
    std::map<int,int>* merge=new std::map<int,int>;
    (*merge)[states[cur]]++;
    if(stamounts[states[cur]]==1){
        merge->erase(states[cur]);
    }
    for(int i:edges[cur]){
        if(i==parent)continue;
        parents[i]=cur;
        std::map<int,int>* newm=dfs(i,cur);
        if(newm->size()>merge->size())std::swap(merge,newm);
        for(std::pair<int,int> j:*newm){
            (*merge)[j.first]+=j.second;
            if((*merge)[j.first]==stamounts[j.first])merge->erase(j.first);
        }
        delete newm;
    }
    if(merge->empty()){
        separable[cur]=1;
    }
    return merge;
}
int dfs2(int cur){
    int nhsep=0;
    for(int i:edges[cur]){
        if(i==parents[cur])continue;
        nhsep+=dfs2(i);
    }
    if(cur==0&&nhsep<=1){
        nleaves++;//if root is a leaf
    }else if(separable[cur]){
        if(!nhsep)nleaves++;
        nhsep=1;
    }
    
    return nhsep;
}
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,k;
    std::cin>>n>>k;
    edges.resize(n);
    parents.resize(n);
    stamounts.resize(k);
    separable.resize(n);
    for(int i=1;i<n;i++){
        int a,b;
        std::cin>>a>>b;
        a--,b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        x--;
        states.push_back(x);
        stamounts[x]++;
    }
    std::map<int,int>* res=dfs(0);
    delete res;
    dfs2(0);
    std::cout<<(nleaves==1?0:(nleaves+1)/2)<<'\n';
}

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