Submission #1111146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111146		Ghulam_Junaid	Village (BOI20_village)	C++17	12 / 100	1068 ms	2640 KiB

Village

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e3 + 10;
int n, dist[N][N], marked, longest, smallest;
int ans1[N], ans2[N];
vector<int> g[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<int> vec;
    for (int i = 1; i <= n; i ++)
        vec.push_back(i);
 
    smallest = 1e9;
    do{
        bool cont = 0;
        for (int i = 0; i < n; i ++)
            if (vec[i] == i + 1)
                cont = 1;
 
        if (cont) continue;
 
        int tmp = 0;
        for (int i = 0; i < n; i ++)
            tmp += dist[i + 1][vec[i]];
 
        if (smallest > tmp){
            for (int i = 1; i <= n; i ++)
                ans1[i] = vec[i - 1];
            smallest = tmp;
        }
        if (longest < tmp){
            for (int i = 1; i <= n; i ++)
                ans2[i] = vec[i - 1];
            longest = tmp;
        }
    }while(next_permutation(vec.begin(), vec.end()));
 
    cout << smallest << " " << longest << endl;
    for (int i = 1; i <= n; i ++)
        cout << ans1[i] << " ";
    cout << endl;
    for (int i = 1; i <= n; i ++)
        cout << ans2[i] << " ";
    cout << endl;
}
 
/*
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e3 + 10;
int n, dist[N][N], marked, longest, smallest;
vector<int> g[N];
int mark[N], ans[N], tmp, mxh[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);
            }
        }
    }
}
 
void pre_dfs(int v, int p = -1){
    mxh[v] = 0;
    for (int u : g[v]){
        if (u == p) continue;
        pre_dfs(u, v);
        mxh[v] = max(mxh[v], mxh[u] + 1);
    }
}
 
vector<int> path;
vector<pair<int, int>> adj;
void dfs(int v, int p = -1){
    path.push_back(v);
    adj.clear();
    for (int u : g[v]){
        if (u == p) continue;
        adj.push_back({mxh[u], u});
    }
    
    sort(adj.begin(), adj.end());
    reverse(adj.begin(), adj.end());
 
    for (auto [x, u] : adj)
        dfs(u, v);
}
 
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 = path[i];
        int v = path[(i + 1) % n];
        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;
    }
 
 
    smallest = 1e9;
    for (int i = 1; i <= n; i ++){
        tmp = 0;
        path.clear();
 
        pre_dfs(i);
        dfs(i);
 
        for (int i = 0; i < n; i ++){
            int u = path[i];
            int v = path[(i + 1) % n];
            tmp += dist[u][v];
        }
 
        if (smallest > tmp){
            smallest = tmp;
            for (int i = 0; i < n; i ++){
                int u = path[i];
                int v = path[(i + 1) % n];
                ans[u] = v;
            }
        }
    }
 
 
    cout << smallest << " " << longest << endl;
    for (int i = 1; i <= n; i ++)
        cout << ans[i] << " ";
    cout << endl;
    for (int i = 1; i <= n; i ++)
        cout << mark[i] << " ";
    cout << endl;
}
*/

• Subtask 1: 12 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50