제출 #602883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
602883		cadmiumsky	Newspapers (CEOI21_newspapers)	C++14	0 / 100	1 ms	340 KiB

newspapers

#include <bits/stdc++.h>

using namespace std;
using tii = tuple<int,int,int>;
const int nmax = 1e3 + 5;
vector<int> g[nmax], light[nmax];
int h[nmax], atrleaf[nmax], heavy[nmax];
int ondiam[nmax];

void chmax(tii &l, tii r) {
  l = max(l, r);
}

tii finddiam(int node, int f) {
  tii rez = {1, node, node};
  atrleaf[node] = node;
  h[node] = 1;
  for(auto x : g[node]) {
    if(x == f) continue;
    chmax(rez, finddiam(x, node));
    if(h[x] + 1 > h[node]) {
      h[node] = h[x] + 1;
      atrleaf[node] = atrleaf[x];
    }
  }
  int other = 0, atr = node;
  for(auto x : g[node]) {
    if(x == f || atrleaf[node] == atrleaf[x])
      continue;
    if(h[x] > other) {
      other = h[x];
      atr = atrleaf[x];
    }
  }
  chmax(rez, tii{other + h[node], atrleaf[node], atr});
  return rez;
  
}
static bool markdiam(int node, int f, int rez) {
  if(node == rez) {
    heavy[node] = -1;
    return 1;
  }
  ondiam[node] = 1;
  for(auto x : g[node]) {
    if(x == f)
      continue;
    if(markdiam(x, node, rez)) {
      heavy[node] = x;
      return 1;
    }
  }
  ondiam[node] = 0;
  return 0;
}
vector<int> rez;
  int len, l, r;
void commence(int node, bool state = 0) {
  if(heavy[node] == -1)
    return;
  if(state == 0) {
    commence(heavy[node], 0);
    rez.push_back(node);
    for(auto x : light[node])
      rez.push_back(x),
      rez.push_back(node);
    if(node != l)
      return;
    commence(node, 1);
    return;
  }
  if(state == 1) {
    rez.push_back(node);
    for(auto x : light[node])
      rez.push_back(x),
      rez.push_back(node);
    commence(heavy[node], 1);
    return;
  }
  
}

int main() {  
  int n, m;
  cin >> n >> m;
  for(int i = 0, x, y; i < m; i++) {
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  if(m >= n) {
    cout << "NO\n";
    return 0;
  }
  tie(len, l, r) = finddiam(1, 1); 
  markdiam(l, l, r);
  finddiam(l, l);
  for(int i = 1; i <= n; i++) {
    if(ondiam[i] == 1) {
      for(auto x : g[i]) {
        if(ondiam[x])
          continue;
        if(h[x] > 2) {
          cout << "NO\n";
          return 0;
        }
        if(h[x] == 2)
          light[i].push_back(x);
      }
    }
  }
  commence(l);
  //cerr << l << ' ' << r<< '\n';
  cout << "YES\n" << rez.size() << '\n';
  for(auto x : rez)
    cout << x<< ' ';
  cout << '\n';
}
//4 1 6 1 2 3 3 2 1 6 1 4 

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