Submission #1067441

#TimeUsernameProblemLanguageResultExecution timeMemory
1067441AndreyNewspapers (CEOI21_newspapers)C++14
0 / 100
1 ms860 KiB
#include<bits/stdc++.h> using namespace std; vector<int> haha[10000]; int n,m; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; int a,b; for(int i = 0; i < m; i++) { cin >> a >> b; haha[a].push_back(b); haha[b].push_back(a); } if(m > n-1) { cout << "NO" << endl; return 0; } vector<int> br(n+1); for(int i = 1; i <= n; i++) { br[i] = haha[i].size(); } for(int i = 1; i <= n; i++) { if(haha[i].size() == 1) { br[haha[i][0]]--; br[i] = -1; } } vector<int> br1(n+1); for(int i = 1; i <= n; i++) { br1[i] = br[i]; } bool yeah = false; for(int i = 1; i <= n; i++) { if(br1[i] <= 1 && br1[i] >= 0) { for(int v: haha[i]) { br[v]--; } br[i] = -1; } } for(int i = 1; i <= n; i++) { if(br[i] > 2) { yeah = true; } } if(yeah) { cout << "NO\n"; } else { cout << "YES\n"; if(n == 1) { cout << 1 << endl << 1 << endl; return 0; } int y = -1; for(int i = 1; i <= n; i++) { if(br[i] >= 0) { y = i; } } if(y == -1) { cout << 2 << endl; for(int i = 1; i <= n; i++) { if(br1[i] >= 0) { cout << i << " " << i << endl; return 0; } } } vector<int> wow(0); while(true) { wow.push_back(y); bool yeah = false; for(int v: haha[y]) { if(br[v] >= 1 && (wow.size() == 1 || wow[wow.size()-2] != v)) { y = v; yeah = true; break; } } if(!yeah) { break; } } vector<int> ans(0); for(int i = 0; i < wow.size(); i++) { int a = wow[i]; if(i > 0) { ans.push_back(a); } for(int v: haha[a]) { if(br1[v] == 1) { ans.push_back(v); ans.push_back(a); } } } ans.pop_back(); cout << ans.size()*2 << endl; for(int i = 0; i < ans.size(); i++) { cout << ans[i] << " "; } if(ans.size()%2) { for(int i = 0; i < ans.size(); i++) { cout << ans[i] << " "; } } else { for(int i = ans.size()-1; i >= 0; i--) { cout << ans[i] << " "; } } cout << endl; } return 0; }

Compilation message (stderr)

newspapers.cpp: In function 'int main()':
newspapers.cpp:91:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int i = 0; i < wow.size(); i++) {
      |                        ~~^~~~~~~~~~~~
newspapers.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int i = 0; i < ans.size(); i++) {
      |                        ~~^~~~~~~~~~~~
newspapers.cpp:109:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |             for(int i = 0; i < ans.size(); i++) {
      |                            ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...