제출 #790360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790360		1075508020060209tc	Mergers (JOI19_mergers)	C++14	100 / 100	1274 ms	236724 KiB

mergers

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
//#define int long long

int uf[500005];
int fin(int x){
if(uf[x]==x){return x;}
uf[x]=fin(uf[x]);
return uf[x];
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
if(pa==pb){return;}
uf[pa]=pb;
}



int n;int K;
vector<int>e[500005];
int dph[500005];
vector<int>igp[500005];
int rdfn[500005];
vector<int>dfn;
int rmq[22][1500005];
void dfs(int nw,int pa){
dph[nw]=dph[pa]+1;
rdfn[nw]=dfn.size();
dfn.push_back(nw);
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i];
    if(v==pa){continue;}
    dfs(v,nw);
    dfn.push_back(nw);
}
}
bool cmp(int i,int j){
if(rdfn[i]<rdfn[j]){return 1;}
return 0;
}
int lca(int a,int b){
int l=rdfn[a];int r=rdfn[b];
if(r<l){swap(l,r);}
int lg=__lg(r-l+1);
int ret=rmq[lg][l];
if(dph[ret]>dph[rmq[lg][r-(1<<lg)+1]]){
    ret=rmq[lg][r-(1<<lg)+1];
}
return ret;
}
int dp[500005];

void dfs2(int nw,int pa){
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i];
    if(v==pa){continue;}
    dfs2(v,nw);
    if(dp[v]>=1){
        mrg(nw,v);
    }
    dp[nw]+=dp[v];
}
}

set<int>ne[500005];

signed main()
{
    cin>>n>>K;
    for(int i=1;i<=n-1;i++){
        int a;int b;
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }

    dfn.push_back(0);
    dfs(1,0);
    for(int i=1;i<=n;i++){
        int typ;
        cin>>typ;
        igp[typ].push_back(i);
    }
    for(int i=1;i<=K;i++){
        sort(igp[i].begin(),igp[i].end(),cmp);
    }
    for(int i=1;i<dfn.size();i++){
        rmq[0][i]=dfn[i];
    }
    for(int i=1;i<=21;i++){
        for(int j=1;(j+(1<<i)-1)<dfn.size();j++){
            rmq[i][j]=rmq[i-1][j];
            if(dph[rmq[i][j]]>dph[rmq[i-1][j+(1<<(i-1))]]){
                rmq[i][j]=rmq[i-1][j+(1<<(i-1))];
            }
        }
    }

    for(int k=1;k<=K;k++){
        for(int i=1;i<igp[k].size();i++){
            int a=igp[k][i-1];int b=igp[k][i];
            dp[a]++;dp[b]++;
            dp[lca(a,b)]-=2;
        }
        dp[igp[k][0]]++;
        dp[igp[k].back()]++;
        dp[lca(igp[k][0],igp[k].back())]-=2;
    }
    for(int i=1;i<=n;i++){
        uf[i]=i;
    }
    dfs2(1,0);
    for(int i=1;i<=n;i++){
            int nw=fin(i);
        for(int j=0;j<e[i].size();j++){
            int v=fin(e[i][j]);
            if(nw==v){continue;}
            ne[nw].insert(v);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(ne[i].size()==1){ans++;}
    }
    ans=(ans+1)/2;
    cout<<ans<<endl;
}

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

mergers.cpp: In function 'void dfs(int, int)':
mergers.cpp:32:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
mergers.cpp: In function 'void dfs2(int, int)':
mergers.cpp:56:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i=1;i<dfn.size();i++){
      |                 ~^~~~~~~~~~~
mergers.cpp:93:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(int j=1;(j+(1<<i)-1)<dfn.size();j++){
      |                     ~~~~~~~~~~~~^~~~~~~~~~~
mergers.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int i=1;i<igp[k].size();i++){
      |                     ~^~~~~~~~~~~~~~
mergers.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(int j=0;j<e[i].size();j++){
      |                     ~^~~~~~~~~~~~

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