oj.uz

Submission #1102037

# Submission time Handle Problem Language Result Execution time Memory
1102037 2024-10-17T10:30:14 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 : miniPerms)
    {
        bool cur = true;
        for (ll i = 0; i < N; i++)
        {
            if (distance[i][perm[i]] > 2) cur = false;
        }
        if (cur) 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 500 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 508 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 6 ms 1856 KB Output is correct
10 Correct 58 ms 19712 KB Output is correct
11 Correct 43 ms 1932 KB Output is correct
12 Correct 42 ms 1932 KB Output is correct
13 Correct 57 ms 13836 KB Output is correct
14 Runtime error 275 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 1059 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 500 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 508 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 6 ms 1856 KB Output is correct
10 Correct 58 ms 19712 KB Output is correct
11 Correct 43 ms 1932 KB Output is correct
12 Correct 42 ms 1932 KB Output is correct
13 Correct 57 ms 13836 KB Output is correct
14 Runtime error 275 ms 262144 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -