Submission #473962

#	Time	Username	Problem	Language	Result	Execution time	Memory
473962		model_code	Newspapers (CEOI21_newspapers)	C++17	100 / 100	254 ms	8228 KiB

newspapers

#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ll long long

using namespace std;

const int MAXN = 1010;

vector <int> ve[MAXN];
int bio[MAXN];

void impossible() {
    cout << "NO\n";
    exit(0);
}

void dfs(int x, int par) {
    bio[x] = bio[par] + 1;

    for (int y : ve[x]) {
        if (y == par) continue;
        if (bio[y]) impossible();
        dfs(y, x);
    }

    return;
}

int main_path[MAXN];
vector <int> path;
int twig[MAXN];

int rek(int x, int par) {
    int ma = 0;
    for (int y : ve[x]) {
        if (y == par) continue;
        if (main_path[y]) continue;
        ma = max(ma, rek(y, x));
    }
    if (ma == 3) impossible();
    twig[x] = ma;
    return ma + 1;
}

vector <int> out;

void print() {
    cout << "YES\n";
    cout << out.size() << "\n";
    for (int x : out) cout << x + 1 << " ";
    cout << "\n";

    return;
}

int main() {
    int n, m;
    cin >> n >> m;

    if (n == 1) {
        out.push_back(0);
        print();
        return 0;
    }

    if (n == 2) {
        out.push_back(0);
        out.push_back(0);
        print();
        return 0;
    }

    REP(i, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        ve[a].push_back(b);
        ve[b].push_back(a);
    }

    dfs(0, 0);
    int A = -1, dist = -1;
    REP(i, n) {
        if (bio[i] > dist) {
            dist = bio[i];
            A = i;
        }
    }

    memset(bio, 0, sizeof bio);
    dfs(A, A);
    int B = -1;
    dist = -1;
    REP(i, n) {
        if (bio[i] > dist) {
            dist = bio[i];
            B = i;
        }
    }

    int x = B;
    while (x != A) {
        main_path[x] = 1;
        path.push_back(x);
        for (int y : ve[x]) {
            if (bio[y] == bio[x] - 1) {
                x = y;
                break;
            }
        }
    }
    path.push_back(A);
    main_path[A] = 1;

    memset(twig, 0, sizeof twig);
    REP(i, n) {
        if (main_path[i]) twig[i] = rek(i, i) - 1;
    }

    // remove first and last node of path to optimise
    if (path.size() > 1) {
        main_path[path[0]] = 0;
        path.erase(path.begin());

        twig[path[0]] = max(twig[path[0]], 1);
    }
    reverse(path.begin(), path.end());
    if (path.size() > 1) {
        main_path[path[0]] = 0;
        path.erase(path.begin());

        twig[path[0]] = max(twig[path[0]], 1);
    }

    for (int x : path) {
        out.push_back(x);
        if (twig[x] == 2) {
            for (int y : ve[x]) {
                if (main_path[y] || twig[y] == 0) continue;
                out.push_back(y);
                out.push_back(x);
            }
        }
    }

    reverse(path.begin(), path.end());

    for (int x : path) {
        out.push_back(x);
        if (twig[x] == 2) {
            for (int y : ve[x]) {
                if (main_path[y] || twig[y] == 0) continue;
                out.push_back(y);
                out.push_back(x);
            }
        }
    }

    print();

    return 0;
}

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