Submission #529676

#TimeUsernameProblemLanguageResultExecution timeMemory
529676KoDNewspapers (CEOI21_newspapers)C++17
100 / 100
2 ms384 KiB
#include <bits/stdc++.h> using std::vector; using std::array; using std::pair; using std::tuple; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int N, M; std::cin >> N >> M; if (M != N - 1) { std::cout << "NO\n"; return 0; } if (N == 1) { std::cout << "YES\n1\n1\n"; return 0; } vector<vector<int>> graph(N); for (int i = 0; i < M; ++i) { int a, b; std::cin >> a >> b; a -= 1, b -= 1; graph[a].push_back(b); graph[b].push_back(a); } const auto bfs = [&](const int src) { vector<int> dist(N, -1); std::queue<int> que; const auto push = [&](const int u, const int d) { if (dist[u] == -1) { dist[u] = d; que.push(u); } }; push(src, 0); while (!que.empty()) { const int u = que.front(); que.pop(); for (const int v : graph[u]) { push(v, dist[u] + 1); } } return dist; }; const auto dist0 = bfs(0); const int L = std::max_element(dist0.begin(), dist0.end()) - dist0.begin(); const auto distL = bfs(L); const int R = std::max_element(distL.begin(), distL.end()) - distL.begin(); const int D = distL[R]; const auto distR = bfs(R); vector<int> path(D + 1); for (int i = 0; i < N; ++i) { if (distL[i] + distR[i] > D + 4) { std::cout << "NO\n"; return 0; } if (distL[i] + distR[i] == D) { path[distL[i]] = i; } } if (D <= 2) { const int cen = path[D / 2] + 1; std::cout << "YES\n2\n"; std::cout << cen << ' ' << cen << '\n'; return 0; } vector<int> ans; for (int i = 1; i < D; ++i) { const int u = path[i]; ans.push_back(u); for (const int v : graph[u]) { if (graph[v].size() > 1 and distL[v] + distR[v] > D) { ans.push_back(v); ans.push_back(u); } } } for (int i = D - 1; i > 0; --i) { const int u = path[i]; ans.push_back(u); for (const int v : graph[u]) { if (graph[v].size() > 1 and distL[v] + distR[v] > D) { ans.push_back(v); ans.push_back(u); } } } std::cout << "YES\n"; const int n = ans.size(); std::cout << n << '\n'; for (int i = 0; i < n; ++i) { std::cout << ans[i] + 1 << " \n"[i + 1 == n]; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...