Submission #854148

#	Time	Username	Problem	Language	Result	Execution time	Memory
854148		8pete8	Village (BOI20_village)	C++14	56 / 100	59 ms	21804 KiB

Village

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=1e5,mod=1000000007,lg=25,root=1000,inf=1e18;
vector<int>adj[mxn+10];
int subsize[mxn+10],n;
int ansmn[mxn+10],ansmx[mxn+10],up[mxn+10][lg+10],h[mxn+10];
stack<int>sub;
int ans2=0,ans1=0;
bool cmp(int a,int b){return subsize[a]>subsize[b];}
void build(int cur,int p){
    subsize[cur]=1;
    for(auto i:adj[cur]){
        if(i==p)continue;
        build(i,cur);
        ans2+=min(subsize[i],n-subsize[i]);//we claim we can achive this
        subsize[cur]+=subsize[i];
    }
}
int getcen(int cur,int p){
    for(auto i:adj[cur]){
        if(i==p)continue;
        if(subsize[i]*2>n)return getcen(i,cur);
    }
    return cur;
}
void dfs(int cur,int p){
    sub.push(cur);
    for(auto i:adj[cur]){
        if(i==p)continue;
        dfs(i,cur);
    }
}
int solvemn(int cur,int p){
    vector<int>v;
    for(auto i:adj[cur]){
        if(i==p)continue;
        if(solvemn(i,cur))v.pb(i);
    }
    if(v.size()){
        ans1++;
        ansmn[cur]=v[0];
        for(int i=0;i<v.size()-1;i++)ansmn[v[i]]=v[i+1],ans1+=2;
        ansmn[v[v.size()-1]]=cur;
        ans1++;
    }
    else return 1;
    return 0;
}
void solvemx(){
    int node=getcen(1,-1);
    stack<int>st;
    sort(all(adj[node]),cmp);
    for(auto i:adj[node]){
        dfs(i,node);
        int k=st.size();
        k=min(k,subsize[i]);
        for(int j=0;j<k;j++){
            ansmx[sub.top()]=st.top();
            ansmx[st.top()]=sub.top();
            sub.pop();
            st.pop();
        }
        while(!sub.empty()){
            st.push(sub.top());
            sub.pop();
        }
    }
    if(st.size()){
        ansmx[node]=st.top();
        ansmx[st.top()]=node;
        return;
    }
    int g=1;
    if(node==1)g=2;
    ansmx[node]=g;
    ansmx[ansmx[g]]=node;
    //for(auto i:sub)cout<<i<<"\n";
}
int32_t main(){
    fastio
    cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v;cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    fill(ansmn,ansmn+1+n,1);
    fill(ansmx,ansmx+n+1,1);
    build(1,-1);
    solvemx();
    if(solvemn(1,-1)){
        int node=adj[1][0];
        ansmn[1]=node;
        int next=ansmn[node];
        while(ansmn[next]!=node)next=ansmn[next];
        ansmn[next]=1;
        ans1+=2;
    }
    cout<<ans1<<' '<<ans2*2<<'\n';
    for(int i=1;i<=n;i++)cout<<ansmn[i]<<" ";
    cout<<'\n';
    for(int i=1;i<=n;i++)cout<<ansmx[i]<<" ";
}

Compilation message (stderr)

Village.cpp: In function 'long long int solvemn(long long int, long long int)':
Village.cpp:69:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int i=0;i<v.size()-1;i++)ansmn[v[i]]=v[i+1],ans1+=2;
      |                     ~^~~~~~~~~~~

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