Submission #343016

#	Time	Username	Problem	Language	Result	Execution time	Memory
343016		mjhmjh1104	Village (BOI20_village)	C++14	50 / 100	128 ms	24348 KiB

Village

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 100006;

int n, maxDepth[MAX], depth[MAX], childs[MAX];
vector<int> adj[MAX], c[MAX];
int nextShort[MAX], e[MAX], resShort;
int nextLong[MAX];
long long 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);
    }
}

void dfsShort(int x) {
    e[x] = x;
    vector<int> zero;
    for (auto &i: c[x]) {
        if (!childs[i]) zero.push_back(i), e[x] = i;
        else {
            dfsShort(i);
            if (childs[i]) childs[x]--;
            else zero.push_back(i), e[x] = i;
        }
    }
    if (!childs[x]) return;
    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 };
}

pair<pair<int, int>, int> d() {
    depth[0] = 0;
    depthFrom(0);
    int t = farthest(0).first;
    depth[t] = 0;
    depthFrom(t);
    pair<int, int> u = farthest(t);
    return { make_pair(u.first, t), u.second };
}

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);
    for (int i = 0; i < n; i++) childs[i] = (int)c[i].size();
    dfsShort(0);
    if (nextShort[0] == -1) {
        nextShort[0] = c[0][0];
        nextShort[e[c[0][0]]] = 0;
        resShort += 2;
    }
    if (n > 1000) {
        printf("%d 0\n", resShort);
        for (int i = 0; i < n; i++) printf("%d ", nextShort[i] + 1);
        puts("");
        for (int i = 0; i < n - 1; i++) printf("%d ", i + 2);
        printf("1");
        return 0;
    }
    for (int i = 0; i < n / 2 - n % 2; i++) {
        auto it = d();
        resLong += 2 * it.second;
        visited[it.first.first] = visited[it.first.second] = true;
        nextLong[it.first.first] = it.first.second;
        nextLong[it.first.second] = it.first.first;
    }
    if (n % 2) {
        vector<int> v;
        for (int i = 0; i < n; i++) if (!visited[i]) v.push_back(i);
        nextLong[v[0]] = v[1];
        nextLong[v[1]] = v[2];
        nextLong[v[2]] = v[0];
        resLong += 4;
    }
    printf("%d %lld\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 (stderr)

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

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50