Submission #1191319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191319		MateiKing80	Newspapers (CEOI21_newspapers)	C++20	0 / 100	0 ms	328 KiB

newspapers

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int n, m, d[N], pre[N];
vector<int> path, ans, G[N];

int main()
{
    cin >> n >> m;
    if (m >= n)
        cout << "NO\n", exit(0);
    if (n == 1)
        cout << "YES\n1\n1", exit(0);
    if (n == 2)
        cout << "YES\n2\n1 1", exit(0);
    while (m --)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }
    auto bfs = [&]()
    {
        queue<int> Q;
        for (int i = 1; i <= n; i ++)
            if (!d[i])
                Q.push(i);
        while (!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            for (int v : G[u])
                if (!~d[v])
                    Q.push(v), d[v] = d[u] + 1, pre[v] = u;
        }
    };
    memset(d, -1, sizeof(d));
    d[1] = 0;
    bfs();

    int s = max_element(d + 1, d + n + 1) - d;
    memset(d, -1, sizeof(d));
    d[s] = 0;
    bfs();

    int t = max_element(d + 1, d + n + 1) - d;
    for (int i = t; i ^ s; i = pre[i])
            path.push_back(i);
    path.push_back(s);
    memset(d, -1, sizeof(d));
    for (auto i : path)
        d[i] = 0;
    bfs();
    if (*max_element(d + 1, d + n + 1) > 2)
        cout << "NO\n", exit(0);
    for (int i = 1; i + 1 < path.size(); i++)
    {
        for (auto j : G[path[i]])
            if (d[j] && G[j].size() > 1)
                ans.push_back(path[i]), ans.push_back(j);
        ans.push_back(path[i]);
    }
    cout << "YES\n" << 2 * ans.size() << '\n';
    for (auto x : ans)
        cout << x;
    reverse(ans.begin(), ans.end());
    for (auto x : ans)
        cout << x;
}

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