제출 #1353897

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1353897		kokokai	Mergers (JOI19_mergers)	C++20	10 / 100	37 ms	22808 KiB

mergers

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define task "text"

const int N = 5e5+5;
const int LG = 20;
vector<int> adj[N];
int pre[N],dp[N],con[N],name[N];
int n,k;
int S[N];
vector<int> gr[N];
int anc[N][LG],h[N];
void dfs(int u,int p){
    h[u]=h[p]+1;
    anc[u][0]=p;
    for(int lg=1;lg<LG;lg++) anc[u][lg]=anc[anc[u][lg-1]][lg-1];
    for(int v:adj[u]){
        if(v==p) continue;
        dfs(v,u);
    }
}
void dfs1(int u,int p){
    for(int v:adj[u]){
        if(v==p) continue;
        dfs1(v,u);
        pre[u] += pre[v];
    }
}
void dfs2(int u,int p){
    dp[u]=(pre[u]==0);
    for(int v:adj[u]){
        if(v==p) continue;
        dfs2(v,u);
        con[u] += (dp[v]>0);
        if(dp[v]>0) name[u]=v;
        dp[u] += dp[v];
    }
}
int findroot(int u,int p){
    if(con[u] == 1){
        return findroot(name[u],u);
    }
    return u;
}
int lca(int u,int v){
    if(h[u]<h[v]) swap(u,v);
    int d=h[u]-h[v];
    for(int lg=LG-1;lg>=0;lg--){
        if((d&(1<<lg))>0) u=anc[u][lg];
    }
    if(u==v) return u;
    for(int lg=LG-1;lg>=0;lg--){
        if(anc[u][lg] != anc[v][lg]){
            u=anc[u][lg];
            v=anc[v][lg];
        }
    }
    return anc[u][0];
}
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
    }
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        cin>>S[i];
        gr[S[i]].push_back(i);
    }
    dfs(1,0);

    for(int g=1;g<=k;g++){
        if(gr[g].empty()) continue;
        int lc=gr[g][0];
        for(int v:gr[g]) lc=lca(v,lc);
        for(int v:gr[g]){
            pre[v]++;
            pre[lc]--;
        }
    }
    dfs1(1,0);
    pre[1]=1;
    dfs2(1,0);
    int r=findroot(1,0);

    memset(dp,0,sizeof dp);

    dfs2(r,0);
    int leaf=0;
    //cerr<<r<<'\n';
    for(int i=1;i<=n;i++){
        if(pre[i] == 0 && dp[i] == 1) leaf++;
    }
    //cerr<<leaf<<'\n';
    cout<<(leaf+1)/2<<'\n';
}

컴파일 시 표준 에러 (stderr) 메시지

mergers.cpp: In function 'int main()':
mergers.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 10 / 10
• 서브태스크 2: 0 / 24
• 서브태스크 3: 0 / 14
• 서브태스크 4: 0 / 22
• 서브태스크 5: 0 / 30