제출 #1197667

#제출 시각아이디문제언어결과실행 시간메모리
1197667A_M_NamdarNewspapers (CEOI21_newspapers)C++20
0 / 100
9 ms16708 KiB
#include <bits/stdc++.h> using namespace std; const int N = 22; int n, m, d[1 << N], adj[1 << N], par[1 << N]; void input() { cin >> n >> m; if (m != n - 1) { cout << "NO\n"; exit(0); } for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--, v--; adj[1 << u] |= (1 << v); adj[1 << v] |= (1 << u); } } void solve() { for (int mask = 1; mask < (1 << n); mask++) if (__builtin_popcount(mask) > 1) adj[mask] = adj[mask - (mask & -mask)] | adj[mask & -mask]; memset(d, 63, sizeof d); d[(1 << n) - 1] = 0; queue<int> q; q.push((1 << n) - 1); while (!q.empty()) { int u = q.front(); q.pop(); int tmp = adj[u]; for (int i = 0; i < n; i++) if ((tmp >> i) & 1) if (d[tmp ^ (1 << i)] > d[u] + 1) { par[tmp ^ (1 << i)] = u; d[tmp ^ (1 << i)] = d[u] + 1; q.push(tmp ^ (1 << i)); } } if (d[0] > 1e9) cout << "NO\n"; else { cout << "YES\n" << d[0] << '\n'; vector<int> vec; int p = 0; while (p != (1 << n) - 1) { vec.push_back(__builtin_ctz(adj[par[p]] ^ p)); p = par[p]; } for (int i = vec.size() - 1; i >= 0; i--) cout << vec[i] + 1 << ' '; } } int main() { ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0); input(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...