제출 #1214466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214466		aykhn	Newspapers (CEOI21_newspapers)	C++20	4 / 100	11 ms	23880 KiB

newspapers

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 1e6 + 5;
const int LOG = 20;

int n;
int d[MXN], par[MXN], in[MXN];
vector<int> adj[MXN];

int bfs(int s)
{
  fill(d + 1, d + n + 1, inf);
  fill(par + 1, par + n + 1, 0);
  fill(in + 1, in + n + 1, 0);
  queue<int> q;
  q.push(s);
  d[s] = 0;
  while (!q.empty())
  {
    int a = q.front();
    q.pop();
    for (int &v : adj[a])
    {
      if (d[v] > d[a] + 1)
      {
        d[v] = d[a] + 1;
        par[v] = a;
        q.push(v);
      }
    }
  }
  int x = max_element(d + 1, d + n + 1) - d;
  while (x)
  {
    in[x] = 1;
    x = par[x];
  }
  return max_element(d + 1, d + n + 1) - d;
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int m;
  cin >> n >> m;
  if (n == 1)
  {
    cout << "YES\n1\n1\n";
    return 0;
  }
  if (n == 2)
  {
    cout << "YES\n2\n1 1\n";
    return 0;
  }
  if (m > n - 1)
  {
    cout << "NO\n";
    return 0;
  }
  for (int i = 1; i <= m; i++)
  {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  bfs(bfs(1));
  for (int i = 1; i <= n; i++)
  {
    if (!in[i] && adj[i].size() > 1)
    {
      cout << "NO\n";
      return 0;
    }
  }
  cout << "YES\n1\n1\n";
}

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