Submission #932187

#	Time	Username	Problem	Language	Result	Execution time	Memory
932187		Ghulam_Junaid	Village (BOI20_village)	C++17	6 / 100	71 ms	11468 KiB

Village

#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 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50