Submission #343075

#	Time	Username	Problem	Language	Result	Execution time	Memory
343075		mjhmjh1104	Village (BOI20_village)	C++14	100 / 100	200 ms	30180 KiB

Village

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

const int MAX = 100006;

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

vector<int> tmp[MAX];
int tok[MAX];

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

int centroid(int x, int prev = -1) {
    for (auto &i: adj[x]) if (i != prev && sz[i] > n / 2) return centroid(i, x);
    return 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 };
}

void fl(int x, int prev, vector<int> &f) {
    f.push_back(x);
    for (auto &i: adj[x]) if (i != prev) fl(i, x, f);
}

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);
    int ct = centroid(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;
    }
    for (int i = 0; i < n; i++) c[i].clear();
    dfs(ct);
    depth[ct] = 0;
    depthFrom(ct);

    vector<pair<int, int>> v;
    for (auto &i: adj[ct]) v.push_back({ sz[i], i });
    sort(v.begin(), v.end());
    swap(v.front(), v.back());
    int remainSum = 0;
    for (int i = 1; i < (int)v.size(); i++) remainSum += v[i].first;

    queue<pair<int, int>> q;

    vector<pair<int, int>> u;
    for (auto &i: adj[ct]) if (i != v[0].second) u.push_back({ i, sz[i] });

    vector<int> res;
    for (auto &i: u) q.push(i);

    while (!q.empty()) {
        auto t = q.front(); q.pop();
        if (!t.second) continue;
        t.second--;
        res.push_back(t.first);
        q.push(t);
    }

    int k = 0;
    vector<int> r;
    while (remainSum > v[0].first) {
        r.push_back(res[k++]);
        remainSum--;
    }
    while (v[0].first) {
        r.push_back(v[0].second);
        v[0].first--;
        if (remainSum) r.push_back(res[k++]), remainSum--;
    }
    for (int i = 0; i < (int)v.size(); i++) fl(v[i].second, ct, tmp[v[i].second]);

    vector<int> fin;
    for (auto &i: r) {
        resLong += depth[tmp[i][tok[i]]] * 2;
        fin.push_back(tmp[i][tok[i]++]);
    }
    for (int i = 0; i < n - 2; i++) nextLong[fin[i]] = fin[i + 1];
    nextLong[fin[n - 2]] = ct;
    nextLong[ct] = fin[0];

    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:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Village.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

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