제출 #532640

#제출 시각아이디문제언어결과실행 시간메모리
532640qwerasdfzxclNewspapers (CEOI21_newspapers)C++14
100 / 100
19 ms460 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<int> adj[1010]; int h[1010], c[1010]; bool L[1010]; void NO(){ printf("NO\n"); exit(0); } void dfs0(int s, int pa = -1){ h[s] = 1; if (pa==-1) c[s] = 0; L[s] = 1; for (auto &v:adj[s]) if (v!=pa){ L[s] = 0; c[v] = c[s] ^ 1; dfs0(v, s); h[s] = max(h[s], h[v] + 1); } } int r = -1; void chk_valid(int n){ for (int i=1;i<=n;i++){ dfs0(i); int cnt = 0; for (auto &v:adj[i]) if (h[v]>=3) cnt++; if (cnt>=3) NO(); if (cnt==2) r = i; } } vector<int> st; void dfs2(int s, int pa){ if (L[s]) return; bool flag = 0; for (auto &v:adj[s]) if (v!=pa && !L[v]){ st.push_back(s); dfs2(v, s); flag = 1; } if (!flag) st.push_back(s); } bool cmp(int x, int y){return h[x] > h[y];} int main(){ int n, m; scanf("%d %d", &n, &m); if (m>n-1) NO(); if (n<=2){ //naive here if (n==1) printf("YES\n1\n1\n"); else printf("YES\n2\n1 1\n"); return 0; } for (int i=0;i<m;i++){ int x, y; scanf("%d %d", &x, &y); adj[x].push_back(y); adj[y].push_back(x); } chk_valid(n); if (r==-1){ for (int i=1;i<=n;i++) if (adj[i].size()>=2) r = i; } assert(r!=-1); //printf("R = %d\n", r); dfs0(r); for (int i=1;i<=n;i++) sort(adj[i].begin(), adj[i].end(), cmp); if (adj[r].size()>=2 && h[adj[r][1]]>=3) swap(adj[r][1], adj[r].back()); for (int i=1;i<=n;i++) reverse(adj[i].begin(), adj[i].end()); vector<int> ans; for (auto &v:adj[r]){ if (h[v]>=3 && v==adj[r].back() && (ans.empty() || ans.back()!=r)) ans.push_back(r); st.clear(); dfs2(v, r); if (h[v]>=3 && v!=adj[r].back()) reverse(st.begin(), st.end()); for (auto &x:st) ans.push_back(x); if (h[v]==2 || (h[v]>=3 && v!=adj[r].back())){ ans.push_back(r); //printf("asdf\n"); } } if (ans.empty()) ans.push_back(r); bool inv = (c[ans[0]]!=c[ans.back()]); printf("YES\n"); printf("%d\n", (int)ans.size()*2); for (auto &x:ans) printf("%d ", x); if (inv) reverse(ans.begin(), ans.end()); for (auto &x:ans) printf("%d ", x); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

newspapers.cpp: In function 'int main()':
newspapers.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
newspapers.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...