Submission #489059

#	Time	Username	Problem	Language	Result	Execution time	Memory
489059		Wayne_Yan	Newspapers (CEOI21_newspapers)	C++17	100 / 100	194 ms	8112 KiB

newspapers

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
/*
   bool chain = true;
   Fl(i, 1, n+1){
   if(edges[i].size() > 2){
   chain = false;
   break;
   }
   }  

   if(chain){
   printf("YES\n");
   printf("%d\n", 2 * (n-2));
   F(n-2) printf("%d ", i+2);
   if(n%2 == 0) RF(n-2) printf("%d ", i+2);
   else F(n-2) printf("%d ", i+2);


   }else{
   printf("YES\n1\n1"); 
   }
*/    
template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int maxN = 1010;
vector<int> edges[maxN];
bool visited[maxN];

int depth1[maxN], mx_depth1 = -1, deepest_node1;
void dfs1(int pos, int fa){ // dfs1 finds one endpoint of the diameter
  for(int i : edges[pos]){
    if(visited[i] || i == fa) continue;
    depth1[i] = depth1[pos] + 1;
    if(mx_depth1 < depth1[i]){
      mx_depth1 = depth1[i];
      deepest_node1 = i;
    }
    dfs1(i, pos);
  }
}

int sz[maxN];
int depth[maxN];

void dfs_sz(int pos, int fa){
  sz[pos] = 1;

  for(int i : edges[pos]){
    if(visited[i] || i == fa) continue;
    depth[i] = depth[pos] + 1;
    dfs_sz(i, pos);
    sz[pos] += sz[i];
  }
}

vector<int> tour;
int cnt;
int nn;
void Euler_Tour(int pos, int fa){
  tour.pb(pos);
  cnt++;
  if(cnt == nn) return;
  bool danger = false;
  for(int i : edges[pos]){
    if(visited[i] || i == fa) continue;
    if(sz[i] >= 2){
      if(!danger){
        danger = true;
      }else{
        printf("NO\n");
        exit(0);
      }
    }
    Euler_Tour(i, pos);
    if(cnt == nn) return;
    tour.pb(pos);
  }
}

signed main(){
  
  int n,m;
  cin >> n >> m;
  nn = n;
  F(m){
    int x,y;
    cin >> x >> y;
    edges[x].pb(y);
    edges[y].pb(x);
  }
  if(n == 1){
    printf("YES\n1\n1");
    exit(0);
  }
  if(n == 2){
    printf("YES\n2\n1 1");
    exit(0);
  }
  if(m == n-1){
    F(n) {
      if(edges[i+1].size() == 1){
        visited[i+1] = true;
        nn--;
        sz[i+1] = 1000000;
      }
    }
    F(n){
      if(!visited[i+1]){
        mx_depth1 = 0;
        deepest_node1 = i+1;
        dfs1(i+1, 0);
        break;
      }
    }
    int root = deepest_node1;
    
    dfs_sz(root, 0);
    
    Fl(i, 1, n+1){
      sort(all(edges[i]), [&](int a, int b){return sz[a] < sz[b];});
    }
    
    Euler_Tour(root, 0);
    printf("YES\n");
    printf("%d\n", 2 * (int)tour.size());
    for(int i : tour){
      printf("%d ", i);
    }
    if(tour.size() % 2 == 0) reverse(all(tour));
    for(int i : tour){
      printf("%d ", i);
    }
  }else{
    printf("NO\n");
  }
  
  return 0;
}

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