oj.uz

Submission #915104

# Submission time Handle Problem Language Result Execution time Memory
915104 2024-01-23T10:55:02 Z Abito Village (BOI20_village) C++14
6 / 100
 514 ms 8280 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 1 ms 600 KB Partially correct
3 Partially correct 1 ms 344 KB Partially correct
4 Partially correct 1 ms 348 KB Partially correct
5 Partially correct 0 ms 348 KB Partially correct
6 Partially correct 1 ms 348 KB Partially correct
7 Partially correct 0 ms 348 KB Partially correct
8 Partially correct 0 ms 488 KB Partially correct
9 Partially correct 1 ms 348 KB Partially correct
10 Partially correct 1 ms 348 KB Partially correct
11 Partially correct 0 ms 348 KB Partially correct
12 Partially correct 0 ms 344 KB Partially correct
13 Partially correct 1 ms 348 KB Partially correct
14 Partially correct 1 ms 344 KB Partially correct
15 Partially correct 1 ms 344 KB Partially correct
16 Partially correct 1 ms 348 KB Partially correct
17 Partially correct 0 ms 348 KB Partially correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 2652 KB Partially correct
2 Partially correct 66 ms 4748 KB Partially correct
3 Partially correct 65 ms 4700 KB Partially correct
4 Incorrect 514 ms 8280 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 1 ms 600 KB Partially correct
3 Partially correct 1 ms 344 KB Partially correct
4 Partially correct 1 ms 348 KB Partially correct
5 Partially correct 0 ms 348 KB Partially correct
6 Partially correct 1 ms 348 KB Partially correct
7 Partially correct 0 ms 348 KB Partially correct
8 Partially correct 0 ms 488 KB Partially correct
9 Partially correct 1 ms 348 KB Partially correct
10 Partially correct 1 ms 348 KB Partially correct
11 Partially correct 0 ms 348 KB Partially correct
12 Partially correct 0 ms 344 KB Partially correct
13 Partially correct 1 ms 348 KB Partially correct
14 Partially correct 1 ms 344 KB Partially correct
15 Partially correct 1 ms 344 KB Partially correct
16 Partially correct 1 ms 348 KB Partially correct
17 Partially correct 0 ms 348 KB Partially correct
18 Partially correct 10 ms 2652 KB Partially correct
19 Partially correct 66 ms 4748 KB Partially correct
20 Partially correct 65 ms 4700 KB Partially correct
21 Incorrect 514 ms 8280 KB Output isn't correct
22 Halted 0 ms 0 KB -