Submission #525597

#	Time	Username	Problem	Language	Result	Execution time	Memory
525597		inwbear	Village (BOI20_village)	C++14	100 / 100	175 ms	34104 KiB

Village

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
int n,a,b,h[100005],par[100005][18],wi[100005][18],ans1,Nnum[100005],rr,k,hf,dp[100005],cc,a1[100005],a2[100005];
LL ans2,ans3;
vector<int>v[100005],o;
int dfs(int N,int pr){
    bool p=true;
    vector<int>nonmat;
    dp[N]=1;
    Nnum[rr]=N;
    rr++;
    h[N]=h[pr]+1;
    wi[N][0]=1;
    par[N][0]=pr;
    for(int i=0;i<v[N].size();i++){
        if(v[N][i]!=pr){
            if(dfs(v[N][i],N)==1)nonmat.pb(v[N][i]);
            dp[N]+=dp[v[N][i]];
            if(dp[v[N][i]]>hf)p=false;
        }
    }
    if(p){
        if(n-dp[N]<=hf)cc=N;
    }
    //printf("%d %d\n",N,nonmat.size());
    if(nonmat.size()>0){
        ans1+=nonmat.size()-1;
        if(nonmat.size()%2==0){
            a1[nonmat[0]]=N;
            a1[nonmat[1]]=nonmat[0];
            a1[N]=nonmat[1];
            for(int i=2;i<nonmat.size();i+=2){
                a1[nonmat[i]]=nonmat[i+1];
                a1[nonmat[i+1]]=nonmat[i];
            }
            return 0;
        }
        else{
            a1[nonmat[0]]=N;
            a1[N]=nonmat[0];
            for(int i=1;i<nonmat.size();i+=2){
                a1[nonmat[i]]=nonmat[i+1];
                a1[nonmat[i+1]]=nonmat[i];
            }
            return 0;
        }
    }
    else{
        return 1;
    }
}
void dfs1(int N,int pr){
    o.pb(N);
    for(int i=0;i<v[N].size();i++){
        if(v[N][i]!=pr){
            dfs1(v[N][i],N);
        }
    }
    return;
}
void gen_lca(){
    for(int i=1;i<18;i++){
        for(int j=1;j<=n;j++){
            if(par[j][i-1]!=-1){
                wi[j][i]=wi[j][i-1]+wi[par[j][i-1]][i-1];
                par[j][i]=par[par[j][i-1]][i-1];
            }
        }
    }
    return;
}
int lca(int A,int B){
    if(h[A]<h[B])swap(A,B);
    int diff=h[A]-h[B],re=0;
    for(int i=0;i<18;i++){
        if((diff>>i)&1){
            re+=wi[A][i];
            A=par[A][i];
        }
    }
    if(A==B)return re;
    for(int i=17;i>=0;i--){
        if(par[A][i]!=par[B][i]){
            re+=wi[A][i];
            re+=wi[B][i];
            A=par[A][i];
            B=par[B][i];
        }
    }
    re+=wi[A][0]+wi[B][0];
    return re;
}
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&n);
    hf=n/2;
    ans1=n;
    for(int i=1;i<n;i++){
        scanf("%d %d",&a,&b);
        v[a].pb(b);
        v[b].pb(a);
    }
    for(int i=0;i<18;i++){
        for(int j=1;j<=n;j++){
            par[j][i]=-1;
        }
    }
    k=dfs(1,0);
    ans1+=k;
    if(k==1){
        a1[1]=a1[v[1][0]];
        a1[v[1][0]]=1;
    }
    gen_lca();
    for(int i=1;i<=n;i++){
        ans2+=2*lca(i,cc);
    }
    dfs1(cc,0);
    for(int i=0;i<n;i++){
        //printf("%d ",o[i]);
        a2[o[i]]=o[(i+hf)%n];
    }
    printf("%d %lld\n",ans1,ans2);
    for(int i=1;i<=n;i++)printf("%d ",a1[i]);
    printf("\n");
    for(int i=1;i<=n;i++)printf("%d ",a2[i]);
    printf("\n");
}

Compilation message (stderr)

Village.cpp: In function 'int dfs(int, int)':
Village.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<v[N].size();i++){
      |                 ~^~~~~~~~~~~~
Village.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             for(int i=2;i<nonmat.size();i+=2){
      |                         ~^~~~~~~~~~~~~~
Village.cpp:51:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for(int i=1;i<nonmat.size();i+=2){
      |                         ~^~~~~~~~~~~~~~
Village.cpp: In function 'void dfs1(int, int)':
Village.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0;i<v[N].size();i++){
      |                 ~^~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Village.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 38 / 38
• Subtask 3: 50 / 50