oj.uz

Submission #1101943

# Submission time Handle Problem Language Result Execution time Memory
1101943 2024-10-17T08:19:13 Z yoav_s Village (BOI20_village) C++17
6 / 100
 137 ms 27336 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 = 1e18;
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);
    }
    vtri distances;
    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;
            distances.eb(top.s, p(i, top.f));
            for (ll x : graph[top.f]) dfs.emplace(x, top.s + 1);
        }
    }
    sort(all(distances), greater<tri>());
    vb takenFirst(N,false), takenLast(N, false);
    v availableFirst, availableLast;
    ll res = 0;
    v perm(N);
    for (auto x : distances)
    {
        if (takenFirst[x.s.f] || takenLast[x.s.s]) continue;
        if (availableFirst.size() == 2 && availableFirst[0] + availableFirst[1] - x.s.f == availableLast[0] + availableLast[1] - x.s.s) continue;
        takenFirst[x.s.f] = true;
        takenLast[x.s.s] = true;
        availableFirst = v();
        availableLast = v();
        for (ll i = 0; i < N; i++)
        {
            if (!takenFirst[i]) availableFirst.pb(i);
            if (!takenLast[i]) availableLast.pb(i);
        }
        perm[x.s.f] = x.s.s;
        res += x.f;
    }
    cout << N << " " << res << "\n";
    for (ll i = 0; i < N; i++) cout << "1 ";
    cout << "\n";
    for (ll x : perm) cout << x + 1 << " ";
    cout << "\n";
    return 0;
}

Subtask #1
6.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct
2 Partially correct 1 ms 336 KB Partially correct
3 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 1 ms 340 KB Partially correct
5 Partially correct 1 ms 448 KB Partially correct
6 Partially correct 1 ms 340 KB Partially correct
7 Partially correct 1 ms 340 KB Partially correct
8 Partially correct 1 ms 340 KB Partially correct
9 Partially correct 1 ms 340 KB Partially correct
10 Partially correct 1 ms 340 KB Partially correct
11 Partially correct 1 ms 340 KB Partially correct
12 Partially correct 1 ms 340 KB Partially correct
13 Partially correct 1 ms 504 KB Partially correct
14 Partially correct 1 ms 340 KB Partially correct
15 Partially correct 1 ms 340 KB Partially correct
16 Partially correct 1 ms 340 KB Partially correct
17 Partially correct 1 ms 340 KB Partially correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 1996 KB Partially correct
2 Partially correct 33 ms 7788 KB Partially correct
3 Partially correct 35 ms 7616 KB Partially correct
4 Incorrect 137 ms 27336 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct
2 Partially correct 1 ms 336 KB Partially correct
3 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 1 ms 340 KB Partially correct
5 Partially correct 1 ms 448 KB Partially correct
6 Partially correct 1 ms 340 KB Partially correct
7 Partially correct 1 ms 340 KB Partially correct
8 Partially correct 1 ms 340 KB Partially correct
9 Partially correct 1 ms 340 KB Partially correct
10 Partially correct 1 ms 340 KB Partially correct
11 Partially correct 1 ms 340 KB Partially correct
12 Partially correct 1 ms 340 KB Partially correct
13 Partially correct 1 ms 504 KB Partially correct
14 Partially correct 1 ms 340 KB Partially correct
15 Partially correct 1 ms 340 KB Partially correct
16 Partially correct 1 ms 340 KB Partially correct
17 Partially correct 1 ms 340 KB Partially correct
18 Partially correct 10 ms 1996 KB Partially correct
19 Partially correct 33 ms 7788 KB Partially correct
20 Partially correct 35 ms 7616 KB Partially correct
21 Incorrect 137 ms 27336 KB Output isn't correct
22 Halted 0 ms 0 KB -