oj.uz

Submission #951653

# Submission time Handle Problem Language Result Execution time Memory
951653 2024-03-22T08:53:53 Z temmieowo Village (BOI20_village) C++14
56 / 100
 54 ms 13992 KB 
#include <bits/stdc++.h>
#define int long long
#define fastio ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

const int MAX_N = 100000+10;
const int INF = 2e18;

int n;
int a, b;
vector<vector<int>> G(MAX_N);
bitset<MAX_N> vis;

int total = 0;
int ma = -INF, mi = INF;
vector<int> ma_ans(MAX_N, -1), mi_ans(MAX_N, -1);

pair<int, int> dfs2(int now, int pre){ // <最遠點距離, 最遠點>
    pair<int, int> ret = {0, now};

    for (auto x : G[now]){
        if (x!=pre && vis[x]==0){
            pair<int, int> res = dfs2(x, now);
            ret = max(ret, res);
        }
    }

    ret.first++;
    return ret;
}

void dfs3(int now, int pre){
    // cerr << now << endl;
    for (auto x : G[now]){
        if (x!=pre){
            dfs3(x, now);
        }
    }

    if (mi_ans[now]==-1){
        if (pre!=-1){
            mi_ans[now] = (mi_ans[pre]==-1 ? pre : mi_ans[pre]);
            mi_ans[pre] = now;
        }else{
            mi_ans[now] = mi_ans[G[now].back()];
            mi_ans[G[now].back()] = now;
        }
        total += 2;
    }
    return;
}

void solve2(){

    // input
    cin >> n;
    for (int i=0 ; i<n-1 ; i++){
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // 找到最長的方式
    if (n<=1000){
        total = 0;
        pair<int, int> aa, bb;
        for (int i=0 ; i<n/2 ; i++){
            for (int j=0 ; j<n ; j++){
                if (vis[j]==0){
                    aa = dfs2(j, -1);
                    bb = dfs2(aa.second, -1);

                    vis[aa.second] = 1;
                    vis[bb.second] = 1;
                    total += (bb.first-1)*2;
                    // cerr << "樹直徑：" << aa.second+1 << " & " << bb.second+1 << " 貢獻：" << (bb.first-1)*2 << endl;
                    ma_ans[aa.second] = bb.second;
                    ma_ans[bb.second] = aa.second;
                    break;
                }
            }
        }
        if (n%2==1){
            for (int i=0 ; i<n ; i++){
                if (ma_ans[i]==-1){
                    ma_ans[i] = ma_ans[aa.second];
                    ma_ans[aa.second] = i;
                }
            }
        }
        ma = total;
    }

    // 找到最短的方法
    total = 0;
    dfs3(0, -1);
    mi = total;

    // output
    cout << mi << " " << (ma*(n<=1000)) << "\n";
    for (int i=0 ; i<n ; i++){
        cout << mi_ans[i]+1 << " ";
    }
    cout << "\n";
    for (int i=0 ; i<n ; i++){
        if (n>1000){
            cout << 1 << " ";
        }else{
            cout << ma_ans[i]+1 << " ";
        }
    }
    cout << "\n";

    return;
}

signed main(){

    fastio;

    int t = 1;
    while (t--){
        solve2();
    }

    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 2 ms 4188 KB Output is correct
9 Correct 2 ms 4188 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Correct 2 ms 4188 KB Output is correct
12 Correct 2 ms 4184 KB Output is correct
13 Correct 2 ms 4188 KB Output is correct
14 Correct 2 ms 4188 KB Output is correct
15 Correct 3 ms 4184 KB Output is correct
16 Correct 2 ms 4184 KB Output is correct
17 Correct 2 ms 4188 KB Output is correct

Subtask #2
19.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 3 ms 4188 KB Output is correct
3 Correct 3 ms 4188 KB Output is correct
4 Partially correct 7 ms 4188 KB Partially correct
5 Correct 6 ms 4432 KB Output is correct
6 Correct 6 ms 4184 KB Output is correct
7 Correct 7 ms 4444 KB Output is correct
8 Correct 6 ms 4188 KB Output is correct
9 Correct 5 ms 4188 KB Output is correct
10 Correct 7 ms 4444 KB Output is correct
11 Correct 5 ms 4444 KB Output is correct
12 Correct 5 ms 4188 KB Output is correct
13 Correct 5 ms 4188 KB Output is correct
14 Correct 5 ms 4188 KB Output is correct
15 Correct 5 ms 4188 KB Output is correct
16 Correct 6 ms 4184 KB Output is correct
17 Correct 5 ms 4440 KB Output is correct
18 Correct 5 ms 4188 KB Output is correct
19 Correct 5 ms 4188 KB Output is correct
20 Correct 5 ms 4188 KB Output is correct
21 Correct 6 ms 4188 KB Output is correct
22 Correct 5 ms 4188 KB Output is correct
23 Correct 6 ms 4188 KB Output is correct
24 Correct 5 ms 4440 KB Output is correct
25 Correct 3 ms 4188 KB Output is correct
26 Correct 6 ms 4436 KB Output is correct
27 Correct 5 ms 4188 KB Output is correct
28 Correct 8 ms 4440 KB Output is correct
29 Correct 6 ms 4440 KB Output is correct
30 Correct 5 ms 4184 KB Output is correct

Subtask #3
25.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 2 ms 4188 KB Output is correct
9 Correct 2 ms 4188 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Correct 2 ms 4188 KB Output is correct
12 Correct 2 ms 4184 KB Output is correct
13 Correct 2 ms 4188 KB Output is correct
14 Correct 2 ms 4188 KB Output is correct
15 Correct 3 ms 4184 KB Output is correct
16 Correct 2 ms 4184 KB Output is correct
17 Correct 2 ms 4188 KB Output is correct
18 Correct 2 ms 4184 KB Output is correct
19 Correct 3 ms 4188 KB Output is correct
20 Correct 3 ms 4188 KB Output is correct
21 Partially correct 7 ms 4188 KB Partially correct
22 Correct 6 ms 4432 KB Output is correct
23 Correct 6 ms 4184 KB Output is correct
24 Correct 7 ms 4444 KB Output is correct
25 Correct 6 ms 4188 KB Output is correct
26 Correct 5 ms 4188 KB Output is correct
27 Correct 7 ms 4444 KB Output is correct
28 Correct 5 ms 4444 KB Output is correct
29 Correct 5 ms 4188 KB Output is correct
30 Correct 5 ms 4188 KB Output is correct
31 Correct 5 ms 4188 KB Output is correct
32 Correct 5 ms 4188 KB Output is correct
33 Correct 6 ms 4184 KB Output is correct
34 Correct 5 ms 4440 KB Output is correct
35 Correct 5 ms 4188 KB Output is correct
36 Correct 5 ms 4188 KB Output is correct
37 Correct 5 ms 4188 KB Output is correct
38 Correct 6 ms 4188 KB Output is correct
39 Correct 5 ms 4188 KB Output is correct
40 Correct 6 ms 4188 KB Output is correct
41 Correct 5 ms 4440 KB Output is correct
42 Correct 3 ms 4188 KB Output is correct
43 Correct 6 ms 4436 KB Output is correct
44 Correct 5 ms 4188 KB Output is correct
45 Correct 8 ms 4440 KB Output is correct
46 Correct 6 ms 4440 KB Output is correct
47 Correct 5 ms 4184 KB Output is correct
48 Partially correct 34 ms 8536 KB Partially correct
49 Partially correct 41 ms 9912 KB Partially correct
50 Partially correct 36 ms 10096 KB Partially correct
51 Partially correct 30 ms 8784 KB Partially correct
52 Partially correct 36 ms 9808 KB Partially correct
53 Partially correct 32 ms 9308 KB Partially correct
54 Partially correct 24 ms 8796 KB Partially correct
55 Partially correct 48 ms 13992 KB Partially correct
56 Partially correct 40 ms 11936 KB Partially correct
57 Partially correct 39 ms 11100 KB Partially correct
58 Partially correct 47 ms 10524 KB Partially correct
59 Partially correct 37 ms 10080 KB Partially correct
60 Partially correct 31 ms 9948 KB Partially correct
61 Partially correct 30 ms 10092 KB Partially correct
62 Partially correct 33 ms 10292 KB Partially correct
63 Partially correct 30 ms 10056 KB Partially correct
64 Partially correct 36 ms 10332 KB Partially correct
65 Partially correct 33 ms 10584 KB Partially correct
66 Partially correct 32 ms 9820 KB Partially correct
67 Partially correct 24 ms 8620 KB Partially correct
68 Partially correct 28 ms 9556 KB Partially correct
69 Partially correct 35 ms 10784 KB Partially correct
70 Partially correct 30 ms 10076 KB Partially correct
71 Partially correct 23 ms 8532 KB Partially correct
72 Partially correct 25 ms 9052 KB Partially correct
73 Partially correct 32 ms 10588 KB Partially correct
74 Partially correct 27 ms 9948 KB Partially correct
75 Partially correct 54 ms 10832 KB Partially correct
76 Partially correct 39 ms 9812 KB Partially correct
77 Partially correct 34 ms 10332 KB Partially correct
78 Partially correct 23 ms 8284 KB Partially correct
79 Partially correct 27 ms 8792 KB Partially correct
80 Partially correct 46 ms 10320 KB Partially correct
81 Partially correct 33 ms 10416 KB Partially correct
82 Partially correct 31 ms 10068 KB Partially correct