Submission #698701

#	Time	Username	Problem	Language	Result	Execution time	Memory
698701		cig32	Newspapers (CEOI21_newspapers)	C++17	0 / 100	0 ms	340 KiB

newspapers

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
int n, m;
vector<int> adj[1029];
int dp[1029];
void dpf(int node, int prv) {
  dp[node] = 1;
  for(int x: adj[node]) {
    if(adj[x].size() == 1) continue;
    if(x == prv) continue;
    dpf(x, node);
    dp[node] += dp[x];
  }
}
vector<int> dfs(int node, int prv) {
  int ct=0;
  vector<pair<int, int> > vt;
  for(int x: adj[node]) {
    if(x != prv && adj[x].size() > 1) {
      ct += (dp[x] > 1);
      vt.push_back({dp[x], x});
    }
  }
  if(ct > 2) {
    return {-1};
  }
  if(prv != -1 && ct > 1) {
    return {-1};
  }
  sort(vt.begin(), vt.end());
  if(vt.empty()) {
    return {node};
  }
  int to = vt[vt.size() - 1].second;
  vector<int> res;
  res = dfs(to, node);
  if(res[0] == to) reverse(res.begin(), res.end());
  res.push_back(node);
  for(int i=0; i+1<vt.size(); i++) {
    to = vt[i].second;
    vector<int> get = dfs(to, node);
    if(get[0] != to) reverse(get.begin(), get.end());
    for(int x: get) res.push_back(x);
    if(!(prv == -1 && i+2 == vt.size()))res.push_back(node);
  }
  for(int x: res) if(x == -1) return {-1};
  return res;
}
void solve(int tc) {
  cin >> n >> m;
  for(int i=0; i<m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  if(m != n-1) {
    cout << "NO\n"; return;
  }
  if(n == 2) {
    cout << "YES\n2\n1 1\n"; return;
  }
  for(int rt=1; rt<=n; rt++) {
    if(adj[rt].size() > 1) {
      for(int i=1; i<=n; i++) dp[i] = 0;
      dpf(rt, -1);
      vector<int> seq = dfs(rt, -1);
      if(seq[0] != -1) {
        cout << "YES\n";
        cout << seq.size() * 2 << "\n";
        for(int i=0; i<seq.size(); i++) cout << seq[i] << ' ';
        if(dp[rt] & 1) for(int i=0; i<seq.size(); i++) cout << seq[i] << ' ';
        else for(int i=seq.size()-1; i>=0; i--) cout << seq[i] << ' ';
        cout << "\n"; return;
      }
    }
  }
  cout << "NO\n";
}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Compilation message (stderr)

newspapers.cpp: In function 'std::vector<int> dfs(int, int)':
newspapers.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i=0; i+1<vt.size(); i++) {
      |                ~~~^~~~~~~~~~
newspapers.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if(!(prv == -1 && i+2 == vt.size()))res.push_back(node);
      |                       ~~~~^~~~~~~~~~~~
newspapers.cpp: In function 'void solve(int)':
newspapers.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int i=0; i<seq.size(); i++) cout << seq[i] << ' ';
      |                      ~^~~~~~~~~~~
newspapers.cpp:91:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         if(dp[rt] & 1) for(int i=0; i<seq.size(); i++) cout << seq[i] << ' ';
      |                                     ~^~~~~~~~~~~

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