제출 #522236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522236		blue	Newspapers (CEOI21_newspapers)	C++17	100 / 100	35 ms	4384 KiB

newspapers

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


void answer(vector<int> res)
{
    if((int)res.size() == 0)
    {
        cout << "NO\n";
    }
    else
    {
        cout << "YES\n";
        cout << (int)res.size() << '\n';
        for(int r:res) cout << r << ' ';
        cout << '\n';
    }
}

const int maxN = 1000;
const int INF = 1005;

int N, M;
vector<int> edge[1+maxN];
vector< vector<int> > dist(1+maxN, vector<int>(1+maxN, INF));

int ans = 0;
vector<int> visit;


    int S1 = 1, S2 = 1;


int dfs(int u)
{
    int F = 0;
    for(int v: edge[u])
    {
        if(visit[v]) continue;
        visit[v] = 1;
        F = max(F, dfs(v));
    }
    return 1+F;
}








void dfs1(int s, int u)
{
    for(int v: edge[u])
    {
        if(dist[s][v] <= 1 + dist[s][u]) continue;
        dist[s][v] = 1 + dist[s][u];
        dfs1(s, v);
    }
}

vector<int> leaf(1+maxN, 0);



int main()
{
    cin >> N >> M;

    if(M > N-1)
    {
        cout << "NO\n";
        return 0;
    }

    for(int j = 0; j < M; j++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }


    for(int src = 1; src <= N; src++) //CHECK VALIDITY
    {
        visit = vector<int>(1+N, 0);
        ans = 0;

        visit[src] = 1;
        for(int v: edge[src])
        {
            visit[v] = 1;
            if(dfs(v) >= 3)
                ans++;
        }

        if(ans >= 3)
        {
            cout << "NO\n";
            return 0;
        }
    }








    //VALID!!!

    for(int u = 1; u <= N; u++)
    {
        dist[u][u] = 0;
        dfs1(u, u);
    }

    if(N == 1)
    {
        answer({1});
        return 0;
    }
    else if(N == 2)
    {
        answer({1, 1});
        return 0;
    }

    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            if(dist[i][j] > dist[S1][S2])
            {
                S1 = i;
                S2 = j;
            }
        }
    }
    S1 = edge[S1][0];
    S2 = edge[S2][0];

    vector<int> mainline;
    for(int i = 1; i <= N; i++)
    {
        if(dist[S1][i] + dist[i][S2] == dist[S1][S2])
        {
            mainline.push_back(i);
        }
    }

    sort(mainline.begin(), mainline.end(), [] (int x, int y)
    {
        return dist[S1][x] < dist[S1][y];
    });

    vector<int> anslist;
    for(int u: mainline)
    {
        anslist.push_back(u);
        for(int v: edge[u])
        {
            if(edge[v].size() > 1 && dist[S1][v] + dist[v][S2] > dist[S1][S2])
            {
                anslist.push_back(v);
                anslist.push_back(u);
            }
        }
    }

    vector<int> J;
    for(int q: edge[S2])
    {
        if(edge[q].size() > 1 && dist[S1][q] + dist[q][S2] > dist[S1][S2])
        {
            J.push_back(q);
        }
    }

    vector<int> al2 = anslist;
    if(al2.size() % 2 == 0) reverse(al2.begin(), al2.end());

    if(J.size() > 1)
    swap(al2[0], al2[2]);
    for(int t: al2) anslist.push_back(t);

    answer(anslist);
}

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