Submission #1114867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114867		MisterReaper	Newspapers (CEOI21_newspapers)	C++17	100 / 100	52 ms	8264 KiB

newspapers

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int max_N = int(1000) + 5;

int N, M;
std::vector<int> adj[max_N];

void solve_seperated_diameter_local() {
    for (int n = 1; n <= 10; ++n) {
        std::vector<int> dp(1 << n, -1);
        dp[0] = 0;
        auto dfs = [&](auto&& self, int mask) -> int {
            if (dp[mask] != -1) {
                return dp[mask] == -2 ? n : dp[mask];
            } 
            dp[mask] = -2;
            int ans = n + 100;
            for (int i = 0; i < n; ++i) {
                int nmask = 0;
                for (int j = 0; j < n; ++j) {
                    if (mask >> j & 1 && i != j) {
                        if (j - 1 >= 0) nmask |= (1 << (j - 1));
                        if (j + 1 < n) nmask |= (1 << (j + 1));
                    }
                }
                ans = std::min(ans, self(self, nmask) + 1);
            }
            return dp[mask] = ans;
        };
        int ans = dfs(dfs, (1 << n) - 1);
        std::cout << n << ' ' << ans << '\n';
    }
}

std::vector<int> find_diameter() {
    std::vector<int> dist(N);
    auto dfs = [&](auto&& self, int v, int pr) -> void {
        for (auto u : adj[v]) {
            if (u == pr) {
                continue;
            }
            dist[u] = dist[v] + 1;
            self(self, u, v);
        }
    };
    dfs(dfs, 0, 0);
    int root = std::max_element(dist.begin(), dist.end()) - dist.begin();
    dist.assign(N, 0);
    dfs(dfs, root, root);
    root = std::max_element(dist.begin(), dist.end()) - dist.begin();
    dist.assign(N, 0);
    dfs(dfs, root, root);
    int leaf = std::max_element(dist.begin(), dist.end()) - dist.begin();
    std::vector<int> stk;
    auto find = [&](auto&& self, int v, int pr) -> void {
        stk.emplace_back(v);
        if (v == leaf) {
            return;
        }
        for (auto u : adj[v]) {
            if (u == pr) {
                continue;
            }
            self(self, u, v);
            if (stk.back() == leaf) {
                return;
            }
        }
        stk.pop_back();
    };
    find(find, root, root);

    return stk;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // solve_seperated_diameter_local();

    std::cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int A, B;
        std::cin >> A >> B;
        --A, --B;
        adj[A].emplace_back(B);
        adj[B].emplace_back(A);
    }

    if (M != N - 1) {
        std::cout << "NO\n";
        return 0;
    }

    auto dia = find_diameter();

    std::queue<int> que;
    std::vector<int> dep(N, -1);
    for (auto u : dia) {
        dep[u] = 0;
        que.emplace(u);
    }
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (auto u : adj[v]) {
            if (dep[u] != -1) {
                continue;
            }
            dep[u] = dep[v] + 1;
            que.emplace(u);
        }
    }

    for (int i = 0; i < N; ++i) {
        if (dep[i] >= 3) {
            std::cout << "NO\n";
            return 0;
        }
    }

    if (N == 1) {
        std::cout << "YES\n1\n1\n";
        return 0;
    } 

    dep[dia.front()] = -1;

    int root = dia[1];
    std::vector<int> ans, par(N, -1);
    auto dfs = [&](auto&& self, int v) -> int {
        debug(v);
        if (adj[v].size() == 0) {
            return 0;
        }
        int t = 0, save_child = -1;
        ans.emplace_back(v);
        std::vector<int> w;
        for (auto u : adj[v]) {
            par[u] = v;
            adj[u].erase(std::find(adj[u].begin(), adj[u].end(), v));
            if (dep[u] == 1 && !adj[u].empty()) {
                w.emplace_back(u);
            } else if (dep[u] == 0) {
                save_child = u;
            }
        }
        for (auto u : w) {
            ans.emplace_back(u);
            ans.emplace_back(v);
        }
        if (save_child != -1) {
            self(self, save_child);
        }
        ans.emplace_back(v);
        for (auto u : w) {
            ans.emplace_back(u);
            ans.emplace_back(v);
        }
        return t;
    };
    dfs(dfs, root);

    std::cout << "YES\n";
    std::cout << ans.size() << '\n';
    for (auto u : ans) {
        std::cout << u + 1 << ' ';
    }
    std::cout << '\n';

    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 8 / 8
• Subtask 3: 80 / 80