Submission #659669

#	Time	Username	Problem	Language	Result	Execution time	Memory
659669		zaneyu	Village (BOI20_village)	C++14	100 / 100	172 ms	36932 KiB

Village

/*input 
7
4 2
5 7
3 4
6 3
1 3
4 5
*/ 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
#define ld double
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=2e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e16;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
ll mult(ll a,ll b){
    return ((a%MOD)*(b%MOD))%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
set<int> v[maxn];
vector<int> v2[maxn];
int ans[maxn];
int rev[maxn];
int mx[maxn];
vector<int> pre;
ll mxx=0;
int n;
int dfs(int u,int p){
    pre.pb(u);
    int s=1;
    for(int x:v[u]){
        if(x!=p){
            int z=dfs(x,u);
            mxx+=min(z,n-z);
            s+=z;
        }
    }
    return s;
}
int32_t main(){
    ios::sync_with_stdio(false),cin.tie(0);
    queue<int> q;
    cin>>n;
    REP(i,n-1){
        int a,b;
        cin>>a>>b;
        v[a].insert(b);
        v[b].insert(a);
        v2[a].pb(b);
        v2[b].pb(a);
    }
    REP1(i,n){
        ans[i]=rev[i]=i;
        if(sz(v[i])==1) q.push(i);
    }
    dfs(1,-1);
    int cnt=0;
    while(!q.empty()){
        int z=q.front();
        q.pop();
        if(!sz(v[z]) and ans[z]==z){
            //cout<<z<<'\n';
            int x=v2[z][0];
            int k=rev[x];
            ans[k]=z;
            ans[z]=x;
            rev[x]=z;
            rev[z]=k;
            cnt+=2;
        }
        for(int x:v[z]){
            if(ans[z]==z){
                int k=rev[x];
                ans[k]=z;
                ans[z]=x;
                rev[x]=z;
                rev[z]=k;
                cnt+=2;
            }
            if(v[x].find(z)!=v[x].end()) v[x].erase(z);
            //if(v[z].find(x)!=v[z].end()) v[z].erase(x);
            if(sz(v[x])==1){
                q.push(x);
            }
        }
        v[z].clear();
    }
    
    cout<<cnt<<' '<<2*mxx<<'\n';
    REP1(i,n) cout<<ans[i]<<' ';
  cout<<'\n';
  REP(i,sz(pre)){
    mx[pre[i]]=pre[(i+n/2)%n];
  }
  REP1(i,n) cout<<mx[i]<<' ';
}

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