oj.uz

Submission #932187

# Submission time Handle Problem Language Result Execution time Memory
932187 2024-02-23T05:14:37 Z Ghulam_Junaid Village (BOI20_village) C++17
6 / 100
 71 ms 11468 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int n, dist[N][N], marked, longest;
vector<int> g[N];
int mark[N];

void bfs(int s){
    for (int i = 1; i <= n; i ++)
        dist[s][i] = 1e9;
    dist[s][s] = 0;

    queue<int> q;
    q.push(s);

    while (!q.empty()){
        int v = q.front();
        q.pop();

        for (int u : g[v]){
            if (dist[s][u] > dist[s][v] + 1){
                dist[s][u] = dist[s][v] + 1;
                q.push(u);
            }
        }
    }
}

int main(){
    cin >> n;
    for (int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    assert(n > 1);

    for (int i = 1; i <= n; i ++)
        bfs(i);

    vector<pair<int, pair<int, int>>> vec;
    for (int i = 1; i <= n; i ++)
        for (int j = i + 1; j <= n; j ++)
            vec.push_back({dist[i][j], {i, j}});

    sort(vec.begin(), vec.end());

    for (int i = vec.size() - 1; i >= 0; i --){
        if (n - marked <= 3) break;

        int u = vec[i].second.first;
        int v = vec[i].second.second;

        if (mark[u] or mark[v]) continue;
        
        marked += 2;
        longest += 2 * dist[u][v];

        mark[u] = v;
        mark[v] = u;
    }

    vector<int> left;
    for (int i = 1; i <= n; i ++)
        if (!mark[i]) left.push_back(i);

    if (left.size() == 2){
        mark[left[0]] = left[1];
        mark[left[1]] = left[0];
        longest += 2;
    }
    else {
        mark[left[0]] = left[1];
        mark[left[1]] = left[2];
        mark[left[2]] = left[0];
        longest += 4;
    }

    cout << longest << " " << longest << endl;
    for (int i = 1; i <= n; i ++)
        cout << mark[i] << " ";
    cout << endl;
    for (int i = 1; i <= n; i ++)
        cout << mark[i] << " ";
    cout << endl;
}

Subtask #1
6.0 / 12.0

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

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 3160 KB Partially correct
2 Partially correct 18 ms 4312 KB Partially correct
3 Partially correct 17 ms 4308 KB Partially correct
4 Incorrect 71 ms 11468 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 0 ms 348 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct
3 Correct 1 ms 348 KB Output is correct
4 Partially correct 1 ms 348 KB Partially correct
5 Partially correct 0 ms 348 KB Partially correct
6 Partially correct 0 ms 348 KB Partially correct
7 Correct 1 ms 348 KB Output is correct
8 Partially correct 0 ms 348 KB Partially correct
9 Partially correct 1 ms 344 KB Partially correct
10 Partially correct 0 ms 344 KB Partially correct
11 Partially correct 0 ms 472 KB Partially correct
12 Partially correct 0 ms 344 KB Partially correct
13 Partially correct 0 ms 348 KB Partially correct
14 Correct 0 ms 348 KB Output is correct
15 Partially correct 0 ms 344 KB Partially correct
16 Partially correct 0 ms 344 KB Partially correct
17 Partially correct 1 ms 348 KB Partially correct
18 Partially correct 5 ms 3160 KB Partially correct
19 Partially correct 18 ms 4312 KB Partially correct
20 Partially correct 17 ms 4308 KB Partially correct
21 Incorrect 71 ms 11468 KB Output isn't correct
22 Halted 0 ms 0 KB -