oj.uz

Submission #342992

# Submission time Handle Problem Language Result Execution time Memory
342992 2021-01-03T10:34:02 Z mjhmjh1104 Village (BOI20_village) C++14
0 / 100
 1 ms 364 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 1006;

int n, maxDepth[MAX], depth[MAX];
vector<int> adj[MAX], c[MAX];
int nextShort[MAX], e[MAX], resShort;
int nextLong[MAX], resLong;
bool visited[MAX];

void dfs(int x, int prev = -1) {
    for (auto &i: adj[x]) if (i != prev) {
        c[x].push_back(i);
        dfs(i, x);
        maxDepth[x] = max(maxDepth[i] + 1, maxDepth[x]);
    }
}

void dfsShort(int x) {
    e[x] = x;
    if (!maxDepth[x]) return;
    vector<int> zero;
    for (auto &i: c[x]) {
        if (!maxDepth[i]) zero.push_back(i), e[x] = i;
        else dfsShort(i);
    }
    if (zero.empty()) return;
    nextShort[x] = zero[0];
    for (int i = 0; i < (int)zero.size(); i++) {
        if (i != (int)zero.size() - 1) nextShort[zero[i]] = zero[i + 1];
        else nextShort[zero[i]] = x;
        resShort += 2;
    }
}

void depthFrom(int x, int prev = -1) {
    maxDepth[x] = depth[x];
    for (auto &i: adj[x]) if (i != prev && !visited[i]) {
        depth[i] = depth[x] + 1;
        depthFrom(i, x);
        maxDepth[x] = max(maxDepth[x], maxDepth[i]);
    }
}

pair<int, int> farthest(int x, int prev = -1) {
    for (auto &i: adj[x]) if (i != prev && !visited[i]) {
        if (maxDepth[i] == maxDepth[x]) {
            pair<int, int> t = farthest(i, x);
            return { t.first, t.second + 1 };
        }
    }
    return { x, 0 };
}

int main() {
    scanf("%d", &n);
    fill(nextShort, nextShort + n, -1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0);
    dfsShort(0);
    if (nextShort[0] == -1) {
        nextShort[0] = c[0][0];
        nextShort[e[c[0][0]]] = 0;
        resShort += 2;
    }
    visited[0] = true;
    int k = 0;
    for (int i = 0; i < n - 1; i++) {
        depth[k] = 0;
        depthFrom(k);
        pair<int, int> t = farthest(k);
        nextLong[k] = t.first;
        resLong += t.second;
        k = t.first;
        visited[k] = true;
    }
    for (int i = 0; i < n; i++) visited[i] = false;
    depth[k] = 0;
    depthFrom(k);
    nextLong[k] = 0;
    resLong += depth[0];
    printf("%d %d\n", resShort, resLong);
    for (int i = 0; i < n; i++) printf("%d ", nextShort[i] + 1);
    puts("");
    for (int i = 0; i < n; i++) printf("%d ", nextLong[i] + 1);
}

Compilation message

Village.cpp: In function 'int main()':
Village.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Village.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Incorrect 0 ms 364 KB Integer parameter [name=vi] equals to 0, violates the range [1, 7]
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Integer parameter [name=vi] equals to 0, violates the range [1, 256]
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Incorrect 0 ms 364 KB Integer parameter [name=vi] equals to 0, violates the range [1, 7]
5 Halted 0 ms 0 KB -