oj.uz

Submission #1102022

# Submission time Handle Problem Language Result Execution time Memory
1102022 2024-10-17T10:20:17 Z yoav_s Village (BOI20_village) C++17
0 / 100
 700 ms 262144 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;
    vv miniPerms, maxiPerms;
    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;
            v newPerm(N);
            copy(all(perm), newPerm.begin());
            miniPerms = {newPerm};
        }
        else if (ev == mini)
        {
            v newPerm(N);
            copy(all(perm), newPerm.begin());
            miniPerms.pb(newPerm);
        }
        if (ev > maxi)
        {
            maxi = ev;
            v newPerm(N);
            copy(all(perm), newPerm.begin());
            maxiPerms = {newPerm};
        }
        else if (ev == maxi)
        {
            v newPerm(N);
            copy(all(perm), newPerm.begin());
            maxiPerms.pb(newPerm);
        }
    }
    while (next_permutation(all(perm)));
    bool valid = false;
    for (v perm : maxiPerms)
    {
        ll start = perm[0];
        ll cnt = 1;
        while (start != 0)
        {
            start = perm[start];
            cnt++;
        }
        if (cnt == N) valid = true;
    }
    assert(valid);
    cout << mini << " " << maxi << "\n";
    for (ll x : miniPerms[0]) cout << x + 1 << " ";
    cout << "\n";
    for (ll x : maxiPerms[0]) cout << x + 1 << " ";
    cout << "\n";
}

Subtask #1
0.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 592 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 6 ms 1676 KB Output is correct
10 Correct 59 ms 19708 KB Output is correct
11 Correct 41 ms 2136 KB Output is correct
12 Correct 44 ms 2000 KB Output is correct
13 Correct 64 ms 13808 KB Output is correct
14 Runtime error 255 ms 262144 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 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 592 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 6 ms 1676 KB Output is correct
10 Correct 59 ms 19708 KB Output is correct
11 Correct 41 ms 2136 KB Output is correct
12 Correct 44 ms 2000 KB Output is correct
13 Correct 64 ms 13808 KB Output is correct
14 Runtime error 255 ms 262144 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -