oj.uz

답안 #525593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525593 2022-02-12T05:18:31 Z inwbear Village (BOI20_village) C++14
0 / 100
 2 ms 2652 KB 
#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>mat,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;
    }
    if(nonmat.size()>0){
        ans1+=nonmat.size()-1;
        if(nonmat.size()%2==0){
            for(int i=0;i<nonmat.size();i+=2){
                a1[nonmat[i]]=nonmat[i+1];
                a1[nonmat[i+1]]=nonmat[i];
            }
            return 1;
        }
        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++){
        a2[o[i]]=o[n-i-1];
    }
    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

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

Subtask #1
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Partially correct 2 ms 2636 KB Partially correct
3 Correct 2 ms 2652 KB Output is correct
4 Incorrect 2 ms 2636 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Partially correct 2 ms 2636 KB Partially correct
3 Correct 2 ms 2652 KB Output is correct
4 Incorrect 2 ms 2636 KB Output isn't correct
5 Halted 0 ms 0 KB -