oj.uz

Submission #1102024

# Submission time Handle Problem Language Result Execution time Memory
1102024 2024-10-17T10:22:38 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)
    {
        vb visited(N, false);
        bool cur = true;
        for (ll i=  0; i < N; i++)
        {
            if (visited[i]) continue;
            ll start = perm[i]; visited[start] = true;
            ll cnt = 1;
            while (start != i)
            {
                start = perm[start];
                visited[start] = true;
                cnt++;
            }
            if (cnt > 3) 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 508 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 6 ms 1676 KB Output is correct
10 Correct 61 ms 19884 KB Output is correct
11 Correct 47 ms 1932 KB Output is correct
12 Correct 54 ms 1932 KB Output is correct
13 Correct 58 ms 13688 KB Output is correct
14 Runtime error 296 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 1052 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 508 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 6 ms 1676 KB Output is correct
10 Correct 61 ms 19884 KB Output is correct
11 Correct 47 ms 1932 KB Output is correct
12 Correct 54 ms 1932 KB Output is correct
13 Correct 58 ms 13688 KB Output is correct
14 Runtime error 296 ms 262144 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -