Submission #670471

#	Time	Username	Problem	Language	Result	Execution time	Memory
670471		jamezzz	Village (BOI20_village)	C++17	100 / 100	92 ms	19020 KiB

Village

#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define sf scanf
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
 
#define maxn 100005
 
int n,mnans,deg[maxn],mnpos[maxn],mxpos[maxn],sub[maxn];
long long mxans;
vector<int> AL[maxn];
vector<int> stuff[maxn];

void dfs(int u,int p){
    sub[u]=1;
    for(int v:AL[u]){
        if(v==p)continue;
        dfs(v,u);
        sub[u]+=sub[v];
    }
}

void dfs2(int u,int p,int p2){
    if(p2==-1){
        stuff[u].pb(u);
    }
    else stuff[p2].pb(u);
    for(int v:AL[u]){
        if(v==p)continue;
        dfs2(v,u,(p2==-1)?v:p2);
    }
}

int main(){
    sf("%d",&n);
    for(int i=1;i<n;++i){
        int a,b;sf("%d%d",&a,&b);
        AL[a].pb(b);
        AL[b].pb(a);
        ++deg[a],++deg[b];
    }
    queue<int> q;
    for(int i=1;i<=n;++i){
        mnpos[i]=i;
        if(deg[i]==1)q.push(i);
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        if(mnpos[u]==u){
            int p=-1;
            for(int v:AL[u]){
                if(deg[v]!=0){
                    p=v;
                    break;
                }
            }
            if(p==-1){
                swap(mnpos[AL[u][0]], mnpos[u]);
            }
            else{
                swap(mnpos[p],mnpos[u]);
            }
            mnans+=2;
        }
        for(int v:AL[u]){
            if(deg[v]!=0){
                --deg[v],--deg[u];
                if(deg[v]<=1)q.push(v);
            }
        }
    }
    dfs(1,-1);
    int c=1;
    for(int i=1;i<=n;++i){
        if(i!=1){
            mxans+=2*min(sub[i],n-sub[i]);
        }
        bool pos=true;
        for(int v:AL[i]){
            if(sub[v]<sub[i]&&sub[v]>n/2){
                pos=false;
            }
        }
        if(n-sub[i]>n/2)pos=false;
        if(pos){
            c=i;
        }
    }
    dfs2(c,-1,-1);
    vector<ii> sz;
    for(int i=1;i<=n;++i){
        if(stuff[i].size()!=0)sz.pb({stuff[i].size(),i});
    }
    sort(all(sz),greater<ii>());
    queue<int> to;
    for(int i=1;i<sz.size();++i){
        for(int x:stuff[sz[i].se])to.push(x);
    }
    for(int i=0;i<sz.size();++i){
        for(int x:stuff[sz[i].se]){
            int y=to.front();to.pop();
            mxpos[x]=y;
            to.push(x);
        }
    }
    pf("%d %lld\n",mnans,mxans);
    for(int i=1;i<=n;++i){
        pf("%d ",mnpos[i]);
    }
    pf("\n");
    for(int i=1;i<=n;++i){
        pf("%d ",mxpos[i]);
    }
    pf("\n");
}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=1;i<sz.size();++i){
      |                 ~^~~~~~~~~~
Village.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i=0;i<sz.size();++i){
      |                 ~^~~~~~~~~~
Village.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     sf("%d",&n);
      |       ^
Village.cpp:43:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         int a,b;sf("%d%d",&a,&b);
      |                   ^

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