Submission #593981

#TimeUsernameProblemLanguageResultExecution timeMemory
593981vladislav11Newspapers (CEOI21_newspapers)C++14
20 / 100
2 ms2772 KiB
#include <bits/stdc++.h> using namespace std; int n, m; vector< vector<int> > grp; vector<int> used; void dfs ( int v, int p ) { used[v] = 1; for ( auto& to : grp[v] ) if ( to != p ) { if ( used[to] ) { cout << "NO\n"; exit(0); } dfs( to, v ); } } const int N = 1<<20; pair<int,int> pre[N]; int main () { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; grp.resize( n+1 ); for ( int i=0; i<m; i++ ) { int u, v; cin >> u >> v; grp[u].push_back( v ); grp[v].push_back( u ); } used.assign( n+1, 0 ); dfs( 1, -1 ); if ( n <= 20 ) { queue<int> q; q.push( (1<<n)-1 ); while ( q.size() && pre[0].second == 0 ) { int v = q.front(); q.pop(); int x = 0; for ( int i=0; i<n; i++ ) if ( (v>>i) & 1 ) for ( auto& to : grp[i+1] ) x |= 1 << (to-1); for ( int i=0; i<n; i++ ) if ( pre[ x & (~(1<<i)) ].second == 0 ) { pre[ x & (~(1<<i)) ] = { v, i+1 }; q.push( x & (~(1<<i)) ); if ( ( x & (~(1<<i)) ) == 0 ) break; } } if ( pre[0].second == 0 ) { cout << "NO\n"; return 0; } vector<int> ans; int pos = 0; while ( pos != (1<<n)-1 ) { ans.push_back( pre[pos].second ); pos = pre[pos].first; } cout << "YES\n"; cout << ans.size() << '\n'; while ( ans.size() ) { cout << ans.back() << ' '; ans.pop_back(); } return 0; } cout << "YES\n"; if ( n == 1 ) { cout << "1 1"; return 0; } if ( n == 2 ) { cout << "2 1 1"; return 0; } cout << 2*(n-2) << '\n'; for ( int i=2; i<n; i++ ) cout << i << ' '; for ( int i=n-1; i>1; i-- ) cout << i << ' '; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...