Submission #210844

#	Time	Username	Problem	Language	Result	Execution time	Memory
210844		brcode	Mergers (JOI19_mergers)	C++14	100 / 100	1766 ms	91100 KiB

mergers

#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 5e5+5;
int ans;
int leaves;
vector<int> col[MAXN];
vector<pair<int,int>> edges;
int depth[MAXN];
int dsu[MAXN];
int par[MAXN];
int cnt[MAXN];
vector<int> v1[MAXN];
int find(int curr){
    if(dsu[curr] == curr){
        return curr;
    }
    return dsu[curr] = find(dsu[curr]);
}
void dfs(int curr,int p,int d){
    
    par[curr] = p;
    dsu[curr] = curr;
    depth[curr] = d;
    for(int x:v1[curr]){
        if(x!=p){
            dfs(x,curr,d+1);
        }
    }
}
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v1[x].push_back(y);
        v1[y].push_back(x);
        edges.push_back(make_pair(x,y));
    }
    for(int i=1;i<=n;i++){
        int c;
        cin>>c;
        col[c].push_back(i);
        
    }
    dfs(1,1,1);
    for(int i=1;i<=m;i++){
        for(int j=1;j<col[i].size();j++){
            int a = find(col[i][j-1]);
            int b = find(col[i][j]);
            
            while(a!=b){
                if(depth[a]<depth[b]){
                    swap(a,b);
                }
                
                dsu[a] = find(par[a]);
                a = dsu[a];
                //cout<<find(2)<<endl;
            }
            
        }
    }
    for(auto e:edges){
        int a = find(e.first);
        int b = find(e.second);
        
        if(a!=b){
            cnt[a]++;
            cnt[b]++;
        }
        
    }
    for(int i=1;i<=n;i++){
        if(cnt[i] == 1){
            leaves++;
        }
    }
   
    if(leaves == 1){
        cout<<0<<endl;
        return 0;
    }
    cout<<(leaves+1)/2<<endl;
    
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1;j<col[i].size();j++){
                     ~^~~~~~~~~~~~~~

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