Submission #602945

#	Time	Username	Problem	Language	Result	Execution time	Memory
602945		cadmiumsky	Newspapers (CEOI21_newspapers)	C++14	100 / 100	214 ms	4572 KiB

newspapers

#include <bits/stdc++.h>

using namespace std;
using tii = tuple<int,int,int>;
using pii = pair<int,int>;
const int inf = 1e6 + 5, 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;
    ondiam[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(node == -1)
    return;
  if(state == 0) {
    commence(heavy[node], 0);
    rez.push_back(node);
    for(auto x : light[node])
      //cerr << x << ' ' << node << ' ',
      rez.push_back(x),
      rez.push_back(node);
    if(node != l)
      return;
    if(light[node].size())
      rez.pop_back();
    commence(node, 1);
    return;
  }
  if(state == 1) {
    if(node != l || light[node].size() == 0)
      rez.push_back(node);
    for(auto x : light[node])
      //cerr << x << ' ' << node << ' ',
      rez.push_back(x),
      rez.push_back(node);
    commence(heavy[node], 1);
    
    return;
  }
  
  
}

pii findend(int node, int f) {
  int cnt = 0;
  for(auto x : g[node]) {
    if(x == f) continue;
    if(h[x] > 2)
      cnt++;
  }
  if(cnt >= 2)
    return {-1, inf};
  cnt = 0;
  for(auto x : g[node]) {
    if(x == f) continue;
    if(h[x] > 1)
      cnt++;
  }
  if(cnt == 0)
    return {node, 1};
  for(auto x : g[node]) {
    if(x == f)
      continue;
    if(h[x] > 2) {
      auto tmp = findend(x, node);
      tmp.second++;
      return tmp;
    }
  }
  for(auto x : g[node]) {
    if(x == f)
      continue;
    if(h[x] > 1) {
      auto tmp = findend(x, node);
      tmp.second++;
      return tmp;
    }
  }
}

int main() {  
  int n, m;
  cin >> n >> m;
  if(n == 1) {
    cout << "YES\n1\n1\n";
    return 0;
  }
  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;
        }
      }
    }
  }
  for(int i = 1; i <= n; i++)
    ondiam[i] = 0;
  
  int mn = len, mnl = l, mnr = r;
  for(int i = 1; i <= n; i++) {
    finddiam(i, i);
    tie(r, len) = findend(i, i);
    cerr << i << ": " << r << ' ' << len << '\n';
    if(len < mn) {
      mn = len;
      mnl = i;
      mnr = r;
    }
    //cerr << mnl << ": " << mnr << ' ' << mn << '\n';
  }
  
  tie(l, r, len ) = tii{mnl, mnr, mn};
  markdiam(l, l, r);
  finddiam(l, l);
  for(int i = 1; i <= n; i++) {
    if(ondiam[i] == 1) {
      //cerr << "ceva\n";
      for(auto x : g[i]) {
        if(ondiam[x])
          continue;
        if(h[x] > 2) {
          cout << "NO\n";
          return 0;
        }
        cerr << i << ' ' << x << ' ' << h[x] << '\n';
        
        if(h[x] == 2) {
          light[i].push_back(x);
        }
      }
    }
  }
  if(len == 1 && light[l].size() == 0) {
    cerr << "amog\n";
    cout << "YES\n2\n" << l << ' ' << r << '\n';
    return 0;
  }
  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 

Compilation message (stderr)

newspapers.cpp: In function 'pii findend(int, int)':
newspapers.cpp:131:1: warning: control reaches end of non-void function [-Wreturn-type]
  131 | }
      | ^

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