제출 #1159898

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159898		trandangquang	Mergers (JOI19_mergers)	C++20	100 / 100	560 ms	98920 KiB

mergers

#include<bits/stdc++.h>
using namespace std;

#define ii pair<int,int>
#define fi first
#define se second
#define eb emplace_back

const int N=1000100;

int n,k,a[N],last[N];
int num[N],low[N],Time; bool bridge[N];
int idc[N],deg[N],curc;
vector<ii> ia[N];

void dfs(int u, int lid){
    num[u]=low[u]=++Time;
    for(auto [v,id]:ia[u]) if(id!=lid){
        if(!num[v]){
            dfs(v,id);
            low[u]=min(low[u],low[v]);

            if(low[v]>num[u]){
                bridge[id]=true;
            }
        }
        else{
            low[u]=min(low[u],num[v]);
        }
    }
}
void dfs2(int u){
    idc[u]=curc;
    for(auto [v,id]:ia[u]){
        if(bridge[id]){
            if(idc[v]){
                deg[idc[u]]++; deg[idc[v]]++;
            }
            continue;
        }
        if(!idc[v]) dfs2(v);
    }
}

int main(){
    cin>>n>>k;
    for(int i=1; i<n; ++i){
        int u,v; cin>>u>>v;
        ia[u].eb(v,i);
        ia[v].eb(u,i);
    }
    for(int i=1; i<=n; ++i){
        cin>>a[i];
        if(last[a[i]]!=0){
            ia[last[a[i]]].eb(i,i+n);
            ia[i].eb(last[a[i]],i+n);
        }
        last[a[i]]=i;
    }

    dfs(1,0);
    for(int i=1; i<=n; ++i) if(!idc[i]){
        ++curc;
        dfs2(i);
    }

    int res=0;
    for(int i=1; i<=curc; ++i) res+=deg[i]==1;
    cout<<(res+1)/2<<'\n';
}

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