Submission #1227650

#TimeUsernameProblemLanguageResultExecution timeMemory
1227650Sam_arvandiNewspapers (CEOI21_newspapers)C++20
0 / 100
1099 ms98988 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; random_device device; default_random_engine rng(device()); //#define rand(l, r) uniform_int_distribution<ll> (l, r) (rng) #define mp make_pair #define IOS ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); #define FOR(i, j, n) for (int i = j; i<= n; i++) #define ROF(i, n, j) for (int i = n; i>= j; i--) #define pb push_back #define sep cout << "--------" << endl; #define S second #define F first #define all(a) a.begin(), a.end() /* #pragma GCC optimization("Ofast, unroll-loops") #pragma GCC target("avx2") #pragma GCC target("bmi") #pragma GCC target("bmi2") #pragma GCC target("lzcnt") */ const int mn = 20 + 5, mn2 = (1<<21) + 4; int f[mn2]; vector<int> a[mn], A[mn2]; vector<pii> B[mn2]; queue<int> q; int d[mn2]; vector<int> ans; int main() { IOS; int n, m, u, v, w; cin >> n >> m; FOR(i, 1, m) { cin >> u >> v; a[u].pb(v); a[v].pb(u); } if (m != n-1) { cout << "NO"; return 0; } FOR(mask, 0, (1<<n)-1) { FOR(i, 1, n) { if ((mask&(1<<(i-1)))) { for(auto v: a[i]) { f[mask] = f[mask]|(1<<(v-1)); } } } } FOR(mask, 0, (1<<n)-1) { FOR(i, 1, n) { if ((mask&(1<<(i-1)))) { A[f[mask-(1<<(i-1))]].pb(mask); B[mask].pb(mp(f[mask-(1<<(i-1))], i)); } } } d[0] = 0; FOR(i, 1, (1<<n)-1) { d[i] = 1e9; } q.push(0); while (q.size()) { int u = q.front(); q.pop(); for(auto v: A[u]) { if (d[u]+1 < d[v]) { d[v] = d[u]+1; q.push(v); } } } u = (1<<n)-1; while (u != 0) { for(auto p: B[u]) { v = p.F; w = p.S; if (d[v] == d[u]-1) { ans.pb(w); u = v; break; } } } cout << "YES" << "\n" << d[(1<<n)-1] << "\n"; for(auto v: ans) cout << v << ' '; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...