Submission #1136441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136441		sinataghizadeh	Village (BOI20_village)	C++20	0 / 100	1096 ms	2880 KiB

Village

#include <bits/stdc++.h>
using namespace std;

typedef long long       ll;
typedef pair<ll,ll>     pll;
#define fastio          cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define all(x)          (x).begin(),(x).end()
#define pb              push_back
#define fi              first
#define se              second
#define siz             size()
#define endl            '\n'
const   ll              inf = 1e18;
const   ll              maxn=1e5+5455;
ll cen,n,sub[maxn],p[maxn],a[maxn],ans;
vector<ll>g[maxn];
queue<ll>q;
void dfsz(ll v,ll par) {
        sub[v]=1;
        for(auto u:g[v]){
                if(u==par)continue;
                dfsz(u,v);
                sub[v]+=sub[u];
        }
        if(v!=1)ans+=min(sub[v],n-sub[v]);
        //cout<<sub[v]<<" "<<n-sub[v]-1<<" "<<v<<endl;
}
ll cent(ll v,ll par){
        for(auto u:g[v]){
                if(sub[u]*2>n && u!=par)return cent(u,v);
        }
        return v;
}
void dfs(ll v,ll par,ll r){
        p[v]=r;
        for(auto u:g[v]){
                if(u!=par){
                        dfs(u,v,r);
                }
        }
}
int main() {
        cin>>n;
        for(int i=1;i<n;i++){
                ll u,v;cin>>u>>v;
                g[u].pb(v);
                g[v].pb(u);
                q.push(i);
        }
        q.push(n);
        dfsz(1,-1);
        cen=cent(1,-1);
        for(auto v:g[cen]){
                dfs(v,cen,v);
        }
        cout<<1<<" "<<ans*2<<endl;
        for(int i=1;i<=n;i++)cout<<i<<" ";
        cout<<endl;
        for(int i=1;i<=n;i++){
                while(a[i]==0){
                        ll v=q.front();q.pop();
                        if(p[i]!=p[v])a[i]=v;
                        else q.push(v);
                }
                cout<<a[i]<<" ";
        }
}

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