oj.uz

Submission #1101983

# Submission time Handle Problem Language Result Execution time Memory
1101983 2024-10-17T09:04:44 Z yoav_s Village (BOI20_village) C++17
12 / 100
 700 ms 848 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()

const ll INF = 1e12;
const ll mod = 1e9 + 7;


int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll N;
    cin >> N;
    vv graph(N);
    for (ll i = 0; i < N - 1; i++)
    {
        ll a, b;
        cin >> a >> b; a--; b--;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    vv distance(N, v(N));
    for (ll i =0 ; i < N; i++)
    {
        vb visited(N, false);
        stack<p> dfs;
        dfs.emplace(i, 0);
        while (!dfs.empty())
        {
            auto top = dfs.top();
            dfs.pop();
            if (visited[top.f]) continue;
            visited[top.f] = true;
            distance[i][top.f] = top.s;
            for (ll x : graph[top.f]) dfs.emplace(x, top.s + 1);
        }
    }
    v perm(N);
    for (ll i =0 ; i < N; i++) perm[i] = i;
    ll mini = INF, maxi = -INF;
    v miniPerm(N), maxiPerm(N);
    do
    {
        bool valid = true;
        for (ll i= 0 ; i < N; i++) if (perm[i] == i) valid = false;
        if (!valid) continue;
        ll ev = 0;
        for (ll i = 0; i < N; i++) ev += distance[i][perm[i]];
        if (ev < mini)
        {
            mini = ev;
            copy(all(perm), miniPerm.begin());
        }
        if (ev > maxi)
        {
            maxi = ev;
            copy(all(perm), maxiPerm.begin());
        }
    }
    while (next_permutation(all(perm)));
    cout << mini << " " << maxi << "\n";
    for (ll x : miniPerm) cout << x + 1 << " ";
    cout << "\n";
    for (ll x : maxiPerm) cout << x + 1 << " ";
    cout << "\n";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 5 ms 336 KB Output is correct
10 Correct 40 ms 336 KB Output is correct
11 Correct 36 ms 336 KB Output is correct
12 Correct 41 ms 508 KB Output is correct
13 Correct 38 ms 592 KB Output is correct
14 Correct 42 ms 336 KB Output is correct
15 Correct 40 ms 336 KB Output is correct
16 Correct 42 ms 508 KB Output is correct
17 Correct 49 ms 508 KB Output is correct

Subtask #2
0.0 / 38.0

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

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 5 ms 336 KB Output is correct
10 Correct 40 ms 336 KB Output is correct
11 Correct 36 ms 336 KB Output is correct
12 Correct 41 ms 508 KB Output is correct
13 Correct 38 ms 592 KB Output is correct
14 Correct 42 ms 336 KB Output is correct
15 Correct 40 ms 336 KB Output is correct
16 Correct 42 ms 508 KB Output is correct
17 Correct 49 ms 508 KB Output is correct
18 Execution timed out 1044 ms 848 KB Time limit exceeded
19 Halted 0 ms 0 KB -