답안 #726022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
726022	2023-04-18T10:14:41 Z	Johann	Village (BOI20_village)	C++14	50 / 100	103 ms	15336 KB

Village

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int N;
vvi adj;
vi dpP, dpN;
vi ans_mini;
int miniCheck = 0;

void dfs_mini(int v, int p)
{
    if (sz(adj[v]) == 1 && v != p)
    {
        // leaf
        dpN[v] = 0;
        dpP[v] = INT_MAX;
        return;
    }
    for (int u : adj[v])
        if (u != p)
            dfs_mini(u, v);

    dpN[v] = 0;
    for (int u : adj[v])
        if (u != p)
            dpN[v] += min(dpP[u], dpN[u] + 2);
    for (int u : adj[v])
        if (u != p)
        {
            int tmp = dpN[v] - min(dpP[u], dpN[u] + 2) + min(dpP[u], dpN[u]) + 2;
            dpP[v] = min(dpP[v], tmp);
        }
}
void reconstruct_dpP(int v, int p);
void reconstruct_dpN(int v, int p, int except);

void reconstruct_dpN(int v, int p, int except = -1)
{
    if (sz(adj[v]) == 1 && v != p)
        return; // leaf

    for (int u : adj[v])
    {
        if (u == p)
            continue;
        if (u == except)
        {
            swap(ans_mini[v], ans_mini[u]);
            miniCheck += 2;
            if (dpP[u] < dpN[u])
                reconstruct_dpP(u, v);
            else
                reconstruct_dpN(u, v);
        }
        else if (dpP[u] < dpN[u] + 2)
            reconstruct_dpP(u, v);
        else
        {
            swap(ans_mini[v], ans_mini[u]);
            miniCheck += 2;
            reconstruct_dpN(u, v);
        }
    }
}

void reconstruct_dpP(int v, int p)
{
    if (sz(adj[v]) == 1 && v != p)
        return; // leaf

    int w = -1;
    for (int u : adj[v])
        if (u != p)
        {
            int tmp = dpN[v] - min(dpP[u], dpN[u] + 2) + min(dpP[u], dpN[u]) + 2;
            if (dpP[v] == tmp)
            {
                w = u;
                break;
            }
        }
    reconstruct_dpN(v, p, w);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    adj.resize(N);
    for (int i = 0, a, b; i < N - 1; ++i)
    {
        cin >> a >> b, --a, --b;
        adj[a].push_back(b), adj[b].push_back(a);
    }

    dpP.assign(N, INT_MAX), dpN.assign(N, INT_MAX);

    dfs_mini(0, 0);

    ans_mini.resize(N);
    iota(all(ans_mini), 1);
    reconstruct_dpP(0, 0);

    cout << dpP[0] << " ";
    cout << miniCheck << endl;
    assert(miniCheck == dpP[0]);
    for (int v : ans_mini)
        cout << v << " ";
    cout << endl;

    for (int v : ans_mini)
        cout << v << " ";
    cout << endl;

    return 0;
}

Subtask #1
6.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	1 ms	212 KB	Partially correct
2	Partially correct	1 ms	212 KB	Partially correct
3	Correct	1 ms	212 KB	Output is correct
4	Partially correct	1 ms	212 KB	Partially correct
5	Partially correct	1 ms	320 KB	Partially correct
6	Partially correct	1 ms	212 KB	Partially correct
7	Correct	1 ms	324 KB	Output is correct
8	Partially correct	1 ms	212 KB	Partially correct
9	Partially correct	1 ms	320 KB	Partially correct
10	Partially correct	1 ms	212 KB	Partially correct
11	Partially correct	1 ms	320 KB	Partially correct
12	Partially correct	1 ms	212 KB	Partially correct
13	Partially correct	1 ms	212 KB	Partially correct
14	Correct	1 ms	212 KB	Output is correct
15	Partially correct	1 ms	212 KB	Partially correct
16	Partially correct	1 ms	212 KB	Partially correct
17	Partially correct	1 ms	212 KB	Partially correct

Subtask #2
19.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	1 ms	212 KB	Partially correct
2	Partially correct	1 ms	340 KB	Partially correct
3	Partially correct	1 ms	340 KB	Partially correct
4	Partially correct	1 ms	340 KB	Partially correct
5	Partially correct	2 ms	340 KB	Partially correct
6	Partially correct	1 ms	320 KB	Partially correct
7	Partially correct	1 ms	340 KB	Partially correct
8	Partially correct	2 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	Correct	1 ms	340 KB	Output is correct
13	Partially correct	1 ms	340 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	324 KB	Partially correct
17	Partially correct	1 ms	340 KB	Partially correct
18	Partially correct	1 ms	340 KB	Partially correct
19	Partially correct	1 ms	340 KB	Partially correct
20	Partially correct	1 ms	324 KB	Partially correct
21	Partially correct	1 ms	340 KB	Partially correct
22	Partially correct	1 ms	324 KB	Partially correct
23	Partially correct	1 ms	328 KB	Partially correct
24	Partially correct	1 ms	324 KB	Partially correct
25	Partially correct	1 ms	340 KB	Partially correct
26	Partially correct	1 ms	340 KB	Partially correct
27	Partially correct	1 ms	320 KB	Partially correct
28	Partially correct	1 ms	340 KB	Partially correct
29	Partially correct	1 ms	316 KB	Partially correct
30	Partially correct	1 ms	324 KB	Partially correct

Subtask #3
25.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	1 ms	212 KB	Partially correct
2	Partially correct	1 ms	212 KB	Partially correct
3	Correct	1 ms	212 KB	Output is correct
4	Partially correct	1 ms	212 KB	Partially correct
5	Partially correct	1 ms	320 KB	Partially correct
6	Partially correct	1 ms	212 KB	Partially correct
7	Correct	1 ms	324 KB	Output is correct
8	Partially correct	1 ms	212 KB	Partially correct
9	Partially correct	1 ms	320 KB	Partially correct
10	Partially correct	1 ms	212 KB	Partially correct
11	Partially correct	1 ms	320 KB	Partially correct
12	Partially correct	1 ms	212 KB	Partially correct
13	Partially correct	1 ms	212 KB	Partially correct
14	Correct	1 ms	212 KB	Output is correct
15	Partially correct	1 ms	212 KB	Partially correct
16	Partially correct	1 ms	212 KB	Partially correct
17	Partially correct	1 ms	212 KB	Partially correct
18	Partially correct	1 ms	212 KB	Partially correct
19	Partially correct	1 ms	340 KB	Partially correct
20	Partially correct	1 ms	340 KB	Partially correct
21	Partially correct	1 ms	340 KB	Partially correct
22	Partially correct	2 ms	340 KB	Partially correct
23	Partially correct	1 ms	320 KB	Partially correct
24	Partially correct	1 ms	340 KB	Partially correct
25	Partially correct	2 ms	340 KB	Partially correct
26	Partially correct	1 ms	340 KB	Partially correct
27	Partially correct	1 ms	340 KB	Partially correct
28	Partially correct	1 ms	340 KB	Partially correct
29	Correct	1 ms	340 KB	Output is correct
30	Partially correct	1 ms	340 KB	Partially correct
31	Partially correct	1 ms	340 KB	Partially correct
32	Partially correct	1 ms	340 KB	Partially correct
33	Partially correct	1 ms	324 KB	Partially correct
34	Partially correct	1 ms	340 KB	Partially correct
35	Partially correct	1 ms	340 KB	Partially correct
36	Partially correct	1 ms	340 KB	Partially correct
37	Partially correct	1 ms	324 KB	Partially correct
38	Partially correct	1 ms	340 KB	Partially correct
39	Partially correct	1 ms	324 KB	Partially correct
40	Partially correct	1 ms	328 KB	Partially correct
41	Partially correct	1 ms	324 KB	Partially correct
42	Partially correct	1 ms	340 KB	Partially correct
43	Partially correct	1 ms	340 KB	Partially correct
44	Partially correct	1 ms	320 KB	Partially correct
45	Partially correct	1 ms	340 KB	Partially correct
46	Partially correct	1 ms	316 KB	Partially correct
47	Partially correct	1 ms	324 KB	Partially correct
48	Partially correct	65 ms	8528 KB	Partially correct
49	Partially correct	67 ms	9424 KB	Partially correct
50	Partially correct	91 ms	9344 KB	Partially correct
51	Partially correct	50 ms	7396 KB	Partially correct
52	Partially correct	68 ms	9324 KB	Partially correct
53	Partially correct	53 ms	8420 KB	Partially correct
54	Partially correct	30 ms	7508 KB	Partially correct
55	Partially correct	78 ms	15336 KB	Partially correct
56	Partially correct	103 ms	12108 KB	Partially correct
57	Partially correct	83 ms	11084 KB	Partially correct
58	Partially correct	99 ms	10316 KB	Partially correct
59	Partially correct	69 ms	9432 KB	Partially correct
60	Correct	55 ms	9672 KB	Output is correct
61	Partially correct	49 ms	9780 KB	Partially correct
62	Partially correct	54 ms	9804 KB	Partially correct
63	Partially correct	44 ms	9248 KB	Partially correct
64	Partially correct	68 ms	9700 KB	Partially correct
65	Partially correct	50 ms	9768 KB	Partially correct
66	Partially correct	63 ms	9144 KB	Partially correct
67	Partially correct	53 ms	7196 KB	Partially correct
68	Partially correct	52 ms	8300 KB	Partially correct
69	Partially correct	48 ms	9816 KB	Partially correct
70	Partially correct	46 ms	9212 KB	Partially correct
71	Partially correct	32 ms	6988 KB	Partially correct
72	Partially correct	41 ms	7888 KB	Partially correct
73	Partially correct	46 ms	9888 KB	Partially correct
74	Partially correct	47 ms	9040 KB	Partially correct
75	Partially correct	75 ms	9216 KB	Partially correct
76	Partially correct	75 ms	9216 KB	Partially correct
77	Partially correct	52 ms	9292 KB	Partially correct
78	Partially correct	39 ms	6348 KB	Partially correct
79	Partially correct	40 ms	7372 KB	Partially correct
80	Partially correct	71 ms	9292 KB	Partially correct
81	Partially correct	64 ms	9536 KB	Partially correct
82	Partially correct	45 ms	9548 KB	Partially correct

답안 #726022

Compilation message

Subtask #1 6.0 / 12.0

Subtask #2 19.0 / 38.0

Subtask #3 25.0 / 50.0

Subtask #1
6.0 / 12.0

Subtask #2
19.0 / 38.0

Subtask #3
25.0 / 50.0