Submission #929225

#TimeUsernameProblemLanguageResultExecution timeMemory
929225math_rabbit_1028Newspapers (CEOI21_newspapers)C++14
100 / 100
58 ms4700 KiB
#include <bits/stdc++.h> using namespace std; int N, M; vector<int> adj[1010]; int dep[1010], par[1010], dia[1010]; void DFS(int v, int p=-1) { for (int i = 0; i < adj[v].size(); i++) { int u = adj[v][i]; if (u == p) continue; par[u] = v; dep[u] = dep[v] + 1; DFS(u, v); } } int r = 0; void chk(int v, int p=-1) { if (r >= 3) { cout << "NO\n"; exit(0); } for (int i = 0; i < adj[v].size(); i++) { int u = adj[v][i]; if (u == p) continue; if (dia[u]) continue; r++; chk(u, v); r--; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> N >> M; for (int i = 1; i <= M; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } if (M >= N) { cout << "NO\n"; return 0; } dep[1] = 0; DFS(1); int a = 0, b = 0; for (int i = 1; i <= N; i++) { if (dep[a] < dep[i]) a = i; } dep[a] = 0; par[a] = 0; DFS(a); for (int i = 1; i <= N; i++) { if (dep[b] < dep[i]) b = i; } // cout << a << " " << b << "\n"; int t = b; while (b > 0) { dia[b] = 1; b = par[b]; } b = t; for (int i = 1; i <= N; i++) { if (dia[i]) chk(i); } cout << "YES\n"; if (N == 1) cout << "1\n1\n"; else if (N == 2) cout << "2\n1 1\n"; else { vector<int> ans; while (b > 0) { if (b != t && b != a) { ans.push_back(b); for (int v : adj[b]) { if (dia[v]) continue; if (adj[v].size() > 1) { ans.push_back(v); ans.push_back(b); } } } b = par[b]; } cout << ans.size()*2 << "\n"; for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; reverse(ans.begin(), ans.end()); for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; } return 0; }

Compilation message (stderr)

newspapers.cpp: In function 'void DFS(int, int)':
newspapers.cpp:9:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for (int i = 0; i < adj[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
newspapers.cpp: In function 'void chk(int, int)':
newspapers.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
newspapers.cpp: In function 'int main()':
newspapers.cpp:94:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
      |                         ~~^~~~~~~~~~~~
newspapers.cpp:96:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
      |                         ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...