Submission #1263496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263496		biank	Newspapers (CEOI21_newspapers)	C++20	100 / 100	36 ms	4676 KiB

newspapers

#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define foreach(it, c) for (auto it = begin(c); it != end(c); it++)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using ii = pair<int, int>;

const int INF = 1e9;
const int MAX_N = 1005;

int maxDepth[MAX_N];
vi adj[MAX_N];

int dfs0(int u, int p = -1) {
    int maxi = 0;
    for (int v : adj[u]) if (v != p) {
        maxi = max(maxi, dfs0(v,u) + 1);
    }
    return maxDepth[u] = maxi;
}

int dist[MAX_N], par[MAX_N];

void dfs(int u) {
    for(int v : adj[u]) if (v != par[u]){
        par[v] = u, dist[v] = dist[u] + 1;
        dfs(v);
    }
}

bool check(int n, int m) {
    if (m != n - 1) return false;
    forn(u,n){
        int cnt = 0;
        for (int v : adj[u]){
            if (dfs0(v, u) >= 2) cnt++;
        }
        if (cnt > 2) return false;
    }
    return true;
}

int findFurthest(int s, int n) {
    par[s] = -1, dist[s] = 0;
    dfs(s);
    int u = 0;
    forn(v, n) {
        if (dist[v] > dist[u]) u = v;
    }
    return u;
}

vi findDiameter(int n){
    int u = findFurthest(0, n);
    int v = findFurthest(u, n);
    vi diameter{v};
    while (diameter.back() != u) {
        diameter.pb(par[diameter.back()]);
    }
    return diameter;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    forn(i, m) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    if (!check(n, m)) {
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    if (n <= 2) {
        cout << n << '\n';
        forn(i, n) cout << "1 ";
        cout << '\n';
        return 0;
    }
    vi d = findDiameter(n);
    vi ret;
    forsn(i, 1, sz(d) - 1) {
        int u = d[i];
        ret.pb(u);
        for(int v : adj[u]) if (sz(adj[v]) != 1 && v != d[i + 1] && v != d[i - 1]) {
            ret.pb(v), ret.pb(u);
        }
    }
    cout << 2 * sz(ret) << '\n';
    forn(i, sz(ret)) cout<< ret[i] + 1 << ' ';
    dforn(i, sz(ret)) cout << ret[i] + 1 << ' ';
    cout << '\n';
    
    return 0;
}

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