oj.uz

답안 #525583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525583 2022-02-12T03:30:10 Z inwbear Village (BOI20_village) C++14
0 / 100
 2 ms 2688 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;
LL ans2;
vector<int>v[100005];
int dfs(int N,int pr){
    bool p=true;
    int nonmatch=0;
    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){
            nonmatch+=dfs(v[N][i],N);
            dp[N]+=dp[v[N][i]];
            if(dp[v[N][i]]>hf)p=false;
        }
    }
    if(p){
        //printf("%d\n",N);
        if(n-dp[N]<=hf)cc=N;
    }
    if(nonmatch>0){
        ans1+=nonmatch-1;
        return 0;
    }
    else{
        return 1;
    }
}
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;
    gen_lca();
    for(int i=1;i<=n;i++){
        ans2+=2*lca(i,cc);
    }
    printf("%d %lld\n",ans1,ans2);
    for(int i=1;i<=n;i++)printf("1 ");
    printf("\n");
    for(int i=1;i<=n;i++)printf("1 ");
    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: In function 'int main()':
Village.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Village.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0.0 / 12.0

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

Subtask #2
0.0 / 38.0

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

Subtask #3
0.0 / 50.0

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