oj.uz

Submission #951631

# Submission time Handle Problem Language Result Execution time Memory
951631 2024-03-22T08:02:42 Z temmieowo Village (BOI20_village) C++17
31 / 100
 15 ms 16988 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 = 1000+10;
const int INF = 2e18;

int n;
int a, b;
vector<vector<int>> G(MAX_N);
vector<vector<int>> dis(MAX_N, vector<int>(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);

void dfs(int start, int now, int pre){
    if (pre!=-1) dis[start][now] = dis[start][pre]+1;

    for (auto x : G[now]){
        if (x!=pre){
            dfs(start, x, now);
        }
    }
    return;
}

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].front()];
            mi_ans[G[now].front()] = now;
        }
        total += 2;
    }
    return;
}

void solve1(){
 
    // 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);
    }
 
    // init
    vector<int> v;
    for (int i=0 ; i<n ; i++){
        v.push_back(i);
        dfs(i, i, -1);
    }
    // for (int i=0 ; i<n ; i++){
    //     for (int j=0 ; j<n ; j++){
    //         cerr << dis[i][j] << " ";
    //     }
    //     cerr << "\n";
    // }
    // return;
 
    // process
    int ma = -INF, mi = INF;
    vector<int> ma_ans, mi_ans;
    do{
        int total = 0;
        for (int i=0 ; i<n ; i++){
            if (i==v[i]) goto flag;
            total += dis[i][v[i]];
        }
 
        if (total>ma){
            ma = total;
            ma_ans = v;
        }
        if (total<mi){
            mi = total;
            mi_ans = v;
        }
 
        flag:;
    } while (next_permutation(v.begin(), v.end()));
 
    cout << mi << " " << ma << "\n";
    for (auto x : mi_ans){
        cout << x+1 << " ";
    }
    cout << "\n";
    for (auto x : ma_ans){
        cout << x+1 << " ";
    }
    cout << "\n";
 
    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);
    }

    // 找到最長的方式
    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
    vis = 0;
    cout << mi << " " << ma << "\n";
    for (int i=0 ; i<n ; i++){
        assert(vis[mi_ans[i]]==0);
        assert(i!=mi_ans[i]);
        vis[mi_ans[i]] = 1;
        cout << mi_ans[i]+1 << " ";
    }
    cout << "\n";
    for (int i=0 ; i<n ; i++){
        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 4 ms 8284 KB Output is correct
2 Correct 4 ms 8536 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 5 ms 8284 KB Output is correct
6 Correct 5 ms 8284 KB Output is correct
7 Correct 4 ms 8280 KB Output is correct
8 Correct 4 ms 8280 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct
11 Correct 4 ms 8284 KB Output is correct
12 Correct 4 ms 8284 KB Output is correct
13 Correct 4 ms 8492 KB Output is correct
14 Correct 4 ms 8284 KB Output is correct
15 Correct 4 ms 8284 KB Output is correct
16 Correct 4 ms 8284 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct

Subtask #2
19.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8280 KB Output is correct
2 Correct 6 ms 8540 KB Output is correct
3 Correct 6 ms 8540 KB Output is correct
4 Partially correct 8 ms 8540 KB Partially correct
5 Correct 8 ms 8540 KB Output is correct
6 Correct 8 ms 8540 KB Output is correct
7 Correct 10 ms 8612 KB Output is correct
8 Correct 8 ms 8540 KB Output is correct
9 Correct 8 ms 8540 KB Output is correct
10 Correct 8 ms 8540 KB Output is correct
11 Correct 8 ms 8360 KB Output is correct
12 Correct 8 ms 8540 KB Output is correct
13 Correct 7 ms 8536 KB Output is correct
14 Correct 7 ms 8540 KB Output is correct
15 Correct 7 ms 8540 KB Output is correct
16 Correct 8 ms 8540 KB Output is correct
17 Correct 7 ms 8568 KB Output is correct
18 Correct 10 ms 8540 KB Output is correct
19 Correct 10 ms 8540 KB Output is correct
20 Correct 7 ms 8400 KB Output is correct
21 Correct 7 ms 8540 KB Output is correct
22 Correct 7 ms 8564 KB Output is correct
23 Correct 7 ms 8540 KB Output is correct
24 Correct 7 ms 8372 KB Output is correct
25 Correct 5 ms 8536 KB Output is correct
26 Correct 8 ms 8572 KB Output is correct
27 Correct 7 ms 8544 KB Output is correct
28 Correct 8 ms 8540 KB Output is correct
29 Correct 8 ms 8540 KB Output is correct
30 Correct 7 ms 8540 KB Output is correct

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 4 ms 8536 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 5 ms 8284 KB Output is correct
6 Correct 5 ms 8284 KB Output is correct
7 Correct 4 ms 8280 KB Output is correct
8 Correct 4 ms 8280 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct
11 Correct 4 ms 8284 KB Output is correct
12 Correct 4 ms 8284 KB Output is correct
13 Correct 4 ms 8492 KB Output is correct
14 Correct 4 ms 8284 KB Output is correct
15 Correct 4 ms 8284 KB Output is correct
16 Correct 4 ms 8284 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 5 ms 8280 KB Output is correct
19 Correct 6 ms 8540 KB Output is correct
20 Correct 6 ms 8540 KB Output is correct
21 Partially correct 8 ms 8540 KB Partially correct
22 Correct 8 ms 8540 KB Output is correct
23 Correct 8 ms 8540 KB Output is correct
24 Correct 10 ms 8612 KB Output is correct
25 Correct 8 ms 8540 KB Output is correct
26 Correct 8 ms 8540 KB Output is correct
27 Correct 8 ms 8540 KB Output is correct
28 Correct 8 ms 8360 KB Output is correct
29 Correct 8 ms 8540 KB Output is correct
30 Correct 7 ms 8536 KB Output is correct
31 Correct 7 ms 8540 KB Output is correct
32 Correct 7 ms 8540 KB Output is correct
33 Correct 8 ms 8540 KB Output is correct
34 Correct 7 ms 8568 KB Output is correct
35 Correct 10 ms 8540 KB Output is correct
36 Correct 10 ms 8540 KB Output is correct
37 Correct 7 ms 8400 KB Output is correct
38 Correct 7 ms 8540 KB Output is correct
39 Correct 7 ms 8564 KB Output is correct
40 Correct 7 ms 8540 KB Output is correct
41 Correct 7 ms 8372 KB Output is correct
42 Correct 5 ms 8536 KB Output is correct
43 Correct 8 ms 8572 KB Output is correct
44 Correct 7 ms 8544 KB Output is correct
45 Correct 8 ms 8540 KB Output is correct
46 Correct 8 ms 8540 KB Output is correct
47 Correct 7 ms 8540 KB Output is correct
48 Runtime error 15 ms 16988 KB Execution killed with signal 11
49 Halted 0 ms 0 KB -