Submission #525428

#	Time	Username	Problem	Language	Result	Execution time	Memory
525428		inwbear	Village (BOI20_village)	C++14	0 / 100	2 ms	2648 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;
LL ans2;
vector<int>v[100005];
int dfs(int N,int pr){
    int nonmatch=0;
    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);
    }
    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(){
    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=0;i<n;i++)
    {
        ans2+=lca(Nnum[i],Nnum[(i+hf)%n]);
    }
    printf("%d %lld\n",ans1,ans2);
    for(int i=1;i<n;i++)printf("%d ",i+1);
    printf("1\n");
    for(int i=1;i<n;i++)printf("%d ",i+1);
    printf("1\n");
}

Compilation message (stderr)

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

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