Submission #915104

#	Time	Username	Problem	Language	Result	Execution time	Memory
915104		Abito	Village (BOI20_village)	C++14	6 / 100	514 ms	8280 KiB

Village

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define ll long long
#define y1 YONE
#define free freeee
#define lcm llcm
/*
⠄⠄⠄⠄⢠⣿⣿⣿⣿⣿⢻⣿⣿⣿⣿⣿⣿⣿⣿⣯⢻⣿⣿⣿⣿⣆⠄⠄⠄
⠄⠄⣼⢀⣿⣿⣿⣿⣏⡏⠄⠹⣿⣿⣿⣿⣿⣿⣿⣿⣧⢻⣿⣿⣿⣿⡆⠄⠄
⠄⠄⡟⣼⣿⣿⣿⣿⣿⠄⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿⣿⣇⢻⣿⣿⣿⣿⠄⠄
⠄⢰⠃⣿⣿⠿⣿⣿⣿⠄⠄⠄⠄⠄⠄⠙⠿⣿⣿⣿⣿⣿⠄⢿⣿⣿⣿⡄⠄
⠄⢸⢠⣿⣿⣧⡙⣿⣿⡆⠄⠄⠄⠄⠄⠄⠄⠈⠛⢿⣿⣿⡇⠸⣿⡿⣸⡇⠄
⠄⠈⡆⣿⣿⣿⣿⣦⡙⠳⠄⠄⠄⠄⠄⠄⢀⣠⣤⣀⣈⠙⠃⠄⠿⢇⣿⡇⠄
⠄⠄⡇⢿⣿⣿⣿⣿⡇⠄⠄⠄⠄⠄⣠⣶⣿⣿⣿⣿⣿⣿⣷⣆⡀⣼⣿⡇⠄
⠄⠄⢹⡘⣿⣿⣿⢿⣷⡀⠄⢀⣴⣾⣟⠉⠉⠉⠉⣽⣿⣿⣿⣿⠇⢹⣿⠃⠄
⠄⠄⠄⢷⡘⢿⣿⣎⢻⣷⠰⣿⣿⣿⣿⣦⣀⣀⣴⣿⣿⣿⠟⢫⡾⢸⡟⠄.
⠄⠄⠄⠄⠻⣦⡙⠿⣧⠙⢷⠙⠻⠿⢿⡿⠿⠿⠛⠋⠉⠄⠂⠘⠁⠞⠄⠄⠄
⠄⠄⠄⠄⠄⠈⠙⠑⣠⣤⣴⡖⠄⠿⣋⣉⣉⡁⠄⢾⣦⠄⠄⠄⠄⠄⠄⠄⠄
*/
typedef unsigned long long ull;
using namespace std;
const int N=1e3+5;
int dis[N][N],n,a[N],deg[N];
vector<int> adj[N];
bool b[N];
void dfs(int x,int p,int s,int d){
    dis[s][x]=d;
    for (auto u:adj[x]) if (u!=p) dfs(u,x,s,d+1);
    return;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n;
    for (int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
        deg[x]++;
        deg[y]++;
    }
    for (int i=1;i<=n;i++) dfs(i,0,i,0);
    set<int> leaves;
    for (int i=1;i<=n;i++) if (deg[i]==1) leaves.ep(i);
    while (leaves.size()>1){
        int x=0,y=0,mx=LLONG_MIN;
        for (auto u:leaves){
            for (auto v:leaves){
                if (u==v) continue;
                if (dis[u][v]<=mx) continue;
                x=u,y=v,mx=dis[u][v];
            }
        }
        if (!b[x]){
            a[y]=x;
            b[x]=true;
            leaves.erase(y);
            for (auto u:adj[y]){
                deg[u]--;
                if (deg[u]==1) leaves.ep(u);
            }
        }
        else{
            a[x]=y;
            b[y]=true;
            leaves.erase(x);
            for (auto u:adj[x]){
                deg[u]--;
                if (deg[u]==1) leaves.ep(u);
            }
        }
    }
    for (int i=1;i<=n;i++){
        if (a[i]) continue;
        for (int j=1;j<=n;j++){
            if (b[j]) continue;
            a[i]=j;
            b[j]=true;
            break;
        }
    }
    int x=0;
    for (int i=1;i<=n;i++) x+=dis[i][a[i]];
    cout<<0<<' '<<x<<endl;
    for (int i=1;i<=n;i++) cout<<i<<' ';cout<<endl;
    for (int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;
    return 0;
}

Compilation message (stderr)

Village.cpp: In function 'int32_t main()':
Village.cpp:95:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   95 |     for (int i=1;i<=n;i++) cout<<i<<' ';cout<<endl;
      |     ^~~
Village.cpp:95:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   95 |     for (int i=1;i<=n;i++) cout<<i<<' ';cout<<endl;
      |                                         ^~~~
Village.cpp:96:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   96 |     for (int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;
      |     ^~~
Village.cpp:96:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   96 |     for (int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;
      |                                            ^~~~

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