Submission #675868

#	Time	Username	Problem	Language	Result	Execution time	Memory
675868		toffeeapple	Village (BOI20_village)	C++17	0 / 100	4 ms	5160 KiB

Village

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
typedef pair <int, int> pii;
typedef pair <int, bool> pib;
typedef pair <int, pair <int, int> > pip;
typedef pair <pair <int, int>, int> ppi;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define MP make_pair
#define rep(i,a,b) for (long long i=(a);i<(b);i++)
#define rrep(i,a,b) for (long long i=(a);i>(b);i--)
#define SZ(x) ((long long) sizeof(x))
#define pb push_back  

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fileinp freopen("ain.txt","r",stdin);freopen("aout.txt","w",stdout);

const int dx[]={1,-1 ,0,0,1,-1,-1,1};
const int dy[]={0,0,1,-1,-1,-1,1,1};

const int mod=1e9+7;
const int mod2=998244353;
const int INF=(int)1e18;
const int N=100005;

int n,a,b,minans,maxans,cur,ct=1,curval;
int nb[N],minarr[N],maxarr[N],subtree[N];
bool check;
vector<int>adj[N],adj2[N];
vector<pii>temp;

void dfs(int x,int p){
    subtree[x]=1;
    for(auto it:adj[x]){
        if(it!=p){
            dfs(it,x);
            subtree[x]+=subtree[it];
        }
    }
}

void dfs2(int x,int p,int chk){
    //root tree at centroid
    //adj2 is only for layer under centroid and itself
    if(chk==-1){
        adj2[x].pb(x);
    }else{
        adj2[chk].pb(x);
    }
    for(auto it:adj[x]){
        if(it!=p){
            dfs2(it,x,chk==-1?it:chk);
        }
    }
}

signed main(){
    fastio;
    //fileinp;
    cin>>n;
    rep(i,0,n-1){
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
        nb[a]++;nb[b]++;
    }
    queue<int>q;
    rep(i,1,n+1){
        minarr[i]=i;
        if(nb[i]==1){ //leaf
            q.push(i);
        }
    }
    while(!q.empty()){
        cur=q.front();
        q.pop();
        if(minarr[cur]==cur){
            curval=-1;
            for(auto it:adj[cur]){
                if(nb[it]!=0){
                    curval=it;
                    break;
                }
            }
            if(curval!=-1){
                swap(minarr[cur],minarr[adj[cur][0]]);
            }else if(curval==-1){
                swap(minarr[cur],minarr[curval]);
            }
            minans+=2;
        }
        for(auto it:adj[cur]){
            if(nb[it]!=0){
                nb[it]--;nb[cur]--;
                if(nb[it]<=1){
                    q.push(it);
                }
            }
        }
    }
    dfs(1,-1);
    ct=1;
    rep(i,1,n+1){
        if(i>1){
            maxans+=2*(min(subtree[i],n-subtree[i]));
        }
        check=0;
        for(auto it:adj[i]){
            if(subtree[it]<subtree[i]&&subtree[it]>n/2){
                check=1;
            }
        }
        if(n-subtree[i]>n/2){
            check=1;
        }
        if(!check){
            ct=i;//centroid
        }
    }
    //cout<<ct<<'\n';
    dfs2(ct,-1,-1);
    rep(i,1,n+1){
        if(adj2[i].size()>0){
            temp.pb(MP(adj2[i].size(),i));
        }
    }
    sort(all(temp),greater<pii>());
    queue<int>q2;
    rep(i,1,temp.size()){ //skip 0 (biggest subtree)
        for(auto it:adj2[temp[i].se]){
            q2.push(it);
        }
    }
    rep(i,0,temp.size()){
        for(auto it:adj2[temp[i].se]){
            cur=q2.front();
            q2.pop();
            maxarr[it]=cur;
            //cout<<it<<' '<<cur<<'\n';
            q2.push(it);
        }
    }
    cout<<minans<<' '<<maxans<<'\n';
    rep(i,1,n+1){
        cout<<minarr[i]<<' ';
    }
    cout<<'\n';
    rep(i,1,n+1){
        cout<<maxarr[i]<<' ';
    }
    return 0;
}

Compilation message (stderr)

Village.cpp:10: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("O3")
      | 
Village.cpp:11: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   11 | #pragma GCC optimization ("unroll-loops")
      | 
Village.cpp: In function 'int main()':
Village.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define rep(i,a,b) for (long long i=(a);i<(b);i++)
      |                                          ^
Village.cpp:135:5: note: in expansion of macro 'rep'
  135 |     rep(i,1,temp.size()){ //skip 0 (biggest subtree)
      |     ^~~
Village.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define rep(i,a,b) for (long long i=(a);i<(b);i++)
      |                                          ^
Village.cpp:140:5: note: in expansion of macro 'rep'
  140 |     rep(i,0,temp.size()){
      |     ^~~
Village.cpp:94:47: warning: array subscript -1 is below array bounds of 'long long int [100005]' [-Warray-bounds]
   94 |                 swap(minarr[cur],minarr[curval]);
      |                                  ~~~~~~~~~~~~~^
Village.cpp:94:47: warning: array subscript -1 is below array bounds of 'long long int [100005]' [-Warray-bounds]

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