제출 #971470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971470		Szil	Newspapers (CEOI21_newspapers)	C++17	100 / 100	51 ms	8260 KiB

newspapers

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// #define VERIFY

const int MAXN = 1001;

vector<int> g[MAXN], ans;
int n, m, md = 0, f = 0, cnt = 0, sz[MAXN];

void dfs(int u, int p = -1, int d = 0) {
    if (md < d) {
        md = d;
        f = u;
    }
    for (int v : g[u]) {
        if (v != p) dfs(v, u, d+1);
    }
}

void dfs2(int u, int p = -1) {
    if (cnt != n && g[u].size() != 1) ans.emplace_back(u);
    cnt++;
    for (int v : g[u]) {
        if (v != p) {
            dfs2(v, u);
            if (cnt != n && ans.back() != u) ans.emplace_back(u);
        }
    }
}

int dfs3(int u, int p = -1) {
    sz[u] = 1;
    for (int v : g[u]) {
        if (v != p) sz[u] = max(sz[u], dfs3(v, u)+1);
    }
    sort(g[u].begin(), g[u].end(), [&](int a, int b){
        return sz[a] < sz[b];
    });
    return sz[u];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    if (n - 1 != m) {
        cout << "NO\n";
        return 0;
    }
    bool ok = true;
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int u : g[i]) {
            md = 0;
            dfs(u, i);
            cnt += md >= 2;
        }
        if (cnt >= 3) {
            ok = false;
            break;
        }
    }
    cout << (ok ? "YES\n" : "NO\n");
    if (n == 1) {
        cout << "1\n1\n";
    } else if (n == 2) {
        cout << "2\n1 1\n";
    } else if (ok) {
        md = 0;
        dfs(1);
        dfs3(f);
        dfs2(f);
        vector<int> v;
        for (int i : ans) v.emplace_back(i);
        reverse(ans.begin(), ans.end());
        for (int i : ans) v.emplace_back(i);

#ifdef VERIFY
        assert(n <= 20);
        int bits = (1<<n)-1;
        for (int i : v) {
            int nw = 0;
            for (int j = 0; j < n; j++) {
                if (i != j + 1 && bits & (1<<j)) {
                    for (int u : g[j+1]) {
                        nw |= 1<<(u-1);
                    }
                }
            }
            bits = nw;
        }
        if (__popcount(bits) != 0) throw 1;
#endif

        cout << v.size() << "\n";
        for (int i : v) cout << i << " ";
        cout << "\n";
    }
    return 0;
}

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