oj.uz

Submission #1111146

# Submission time Handle Problem Language Result Execution time Memory
1111146 2024-11-11T15:19:49 Z Ghulam_Junaid Village (BOI20_village) C++17
12 / 100
 700 ms 2640 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 5 ms 336 KB Output is correct
10 Correct 47 ms 512 KB Output is correct
11 Correct 47 ms 336 KB Output is correct
12 Correct 47 ms 336 KB Output is correct
13 Correct 47 ms 516 KB Output is correct
14 Correct 45 ms 508 KB Output is correct
15 Correct 45 ms 504 KB Output is correct
16 Correct 46 ms 336 KB Output is correct
17 Correct 47 ms 500 KB Output is correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 2640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 5 ms 336 KB Output is correct
10 Correct 47 ms 512 KB Output is correct
11 Correct 47 ms 336 KB Output is correct
12 Correct 47 ms 336 KB Output is correct
13 Correct 47 ms 516 KB Output is correct
14 Correct 45 ms 508 KB Output is correct
15 Correct 45 ms 504 KB Output is correct
16 Correct 46 ms 336 KB Output is correct
17 Correct 47 ms 500 KB Output is correct
18 Execution timed out 1068 ms 2640 KB Time limit exceeded
19 Halted 0 ms 0 KB -