oj.uz

Submission #915165

# Submission time Handle Problem Language Result Execution time Memory
915165 2024-01-23T12:30:01 Z 3as8 Village (BOI20_village) C++14
12 / 100
 700 ms 856 KB 
#include <bits/stdc++.h>

#define ll long long
#define endl "\n"
#define fastIO cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false);

#define mid ((l + r) / 2)
#define lChild ((index * 2) + 1)
#define rChild ((index * 2) + 2)

using namespace std;

void dfs(vector<vector<ll> >& graph, vector<ll>& dist, ll startIndex, ll p, ll depth = 0) {

    dist[startIndex] = depth;
    for(auto el : graph[startIndex]) {
        if(el == p) continue;

        dfs(graph, dist, el, startIndex, depth + 1);
    }
}


void solve(ll _) {

    ll n; cin>>n;

    vector<vector<ll> > graph(n);
    for(int i = 0; i < n - 1; i++) {
        ll x, y; cin>>x>>y;
        x--; y--;

        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    vector<vector<ll> > dist(n, vector<ll>(n, -1));

    for(int i = 0; i < n; i++) {
        dfs(graph, dist[i], i, -1);

    }


    vector<ll> arr(n);
    for(int i = 0; i < n; i++) arr[i] = i;

    vector<ll> mnA, mxA;

    ll mn = LLONG_MAX, mx = LLONG_MIN;
    do {

        bool is = true;
        for(int i = 0; i < n; i++) {
            is &= (arr[i] != i);
        }

        if(!is) continue;

        ll d = 0;
        for(int i = 0; i < n; i++) {
            d += dist[i][arr[i]];
        }

        if(mn > d) {
            mnA = arr;
        }
        if(mx < d) {
            mxA = arr;
        }

        mn = min(mn, d);
        mx = max(mx, d);

    } while(next_permutation(arr.begin(), arr.end()));


    cout<<mn<<" "<<mx<<endl;
    for(auto el : mnA) cout<<el + 1<<" ";
    cout<<endl;

    for(auto el : mxA) cout<<el + 1<<" ";
    cout<<endl;
}

int main() {
    fastIO

    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);

    ll t = 0; solve(t);
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 7 ms 460 KB Output is correct
10 Correct 51 ms 344 KB Output is correct
11 Correct 44 ms 348 KB Output is correct
12 Correct 57 ms 600 KB Output is correct
13 Correct 44 ms 348 KB Output is correct
14 Correct 48 ms 444 KB Output is correct
15 Correct 45 ms 344 KB Output is correct
16 Correct 44 ms 348 KB Output is correct
17 Correct 57 ms 440 KB Output is correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1008 ms 856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 7 ms 460 KB Output is correct
10 Correct 51 ms 344 KB Output is correct
11 Correct 44 ms 348 KB Output is correct
12 Correct 57 ms 600 KB Output is correct
13 Correct 44 ms 348 KB Output is correct
14 Correct 48 ms 444 KB Output is correct
15 Correct 45 ms 344 KB Output is correct
16 Correct 44 ms 348 KB Output is correct
17 Correct 57 ms 440 KB Output is correct
18 Execution timed out 1008 ms 856 KB Time limit exceeded
19 Halted 0 ms 0 KB -