oj.uz

Submission #574243

# Submission time Handle Problem Language Result Execution time Memory
574243 2022-06-08T08:39:01 Z tengiz05 Village (BOI20_village) C++17
12 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    int mn = 0;
    
    std::vector<int> w(n, -1), o(n, -1);
    std::vector<int> siz(n, 1);
    
    std::function<void(int, int)> dfs = [&](int u, int p) {
        std::vector<int> a;
        int x = -1;
        for (int v : adj[u]) {
            if (v == p)
                continue;
            dfs(v, u);
            siz[u] += siz[v];
            if (w[v] == -1) {
                a.push_back(v);
            }
            x = v;
        }
        int m = a.size();
        if (m % 2 == 1) {
            for (int i = 0; i < m - 2; i += 2) {
                mn += 4;
                w[a[i]] = a[i + 1];
                w[a[i + 1]] = a[i];
            }
            mn += 2;
            w[u] = a[m - 1];
            w[a[m - 1]] = u;
        } else {
            for (int i = 0; i < m; i += 2) {
                mn += 4;
                w[a[i]] = a[i + 1];
                w[a[i + 1]] = a[i];
            }
            if (m >= 2) {
                w[u] = a[0];
                w[a[0]] = a[1];
                w[a[1]] = u;
            } else if (p == -1) {
                mn += 2;
                w[u] = w[x];
                w[x] = u;
            }
        }
    };
    
    dfs(0, -1);
    
    std::function<int(int, int)> dfs2 = [&](int u, int p) {
        for (int v : adj[u]) {
            if (v != p && siz[v] > n / 2) {
                return dfs2(v, u);
            }
        }
        return u;
    };
    
    int u = dfs2(0, -1);
    
    dfs = [&](int u, int p) {
        siz[u] = 1;
        for (int v : adj[u]) {
            if (v == p)
                continue;
            dfs(v, u);
            siz[u] += siz[v];
        }
    };
    
    dfs(u, -1);
    
    int mx = 0;
    
    std::vector<int> a;
    std::sort(adj[u].begin(), adj[u].end(), [&](int i, int j) {
        return siz[i] > siz[j];
    });
    
    for (int v : adj[u]) {
        if (siz[v] > n / 2) {
            while (true) {}
        }
        std::vector<int> b;
        std::function<void(int, int, int)> dfs = [&](int u, int p, int dep) {
            b.push_back(u);
            mx += dep;
            for (int v : adj[u]) {
                if (v != p) {
                    dfs(v, u, dep + 1);
                }
            }
        };
        dfs(v, u, 1);
        if (b.size() > n / 2) {
            while (true) {}
        }
        while (!a.empty() && !b.empty()) {
            o[a.back()] = b.back();
            o[b.back()] = a.back();
            a.pop_back();
            b.pop_back();
        }
        a.insert(a.end(), b.begin(), b.end());
    }
    
    if (a.empty()) {
        int v = adj[u][0];
        o[u] = o[v];
        o[v] = u;
    } else {
        assert(a.size() == 1);
        o[u] = a[0];
        o[a[0]] = u;
    }
    
    std::cout << mn << " " << 2 * mx << "\n";
    
    for (int i = 0; i < n; i++) {
        std::cout << w[i] + 1 << " \n"[i == n - 1];
    }
    
    for (int i = 0; i < n; i++) {
        std::cout << o[i] + 1 << " \n"[i == n - 1];
    }
    
    return 0;
}

Compilation message

Village.cpp: In function 'int main()':
Village.cpp:115:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |         if (b.size() > n / 2) {
      |             ~~~~~~~~~^~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 0 ms 324 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 324 KB Output is correct
18 Runtime error 1 ms 468 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -