제출 #1227685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227685		Sam_arvandi	Newspapers (CEOI21_newspapers)	C++20	0 / 100	1098 ms	49988 KiB

newspapers

#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<<20) + 4;
int f[mn2], d[mn2];
vector<int> a[mn], A[mn2];
vector<pii> B[mn2];
queue<int> q;
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);
     bool flag = 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;
		    if (v == (1<<n)-1)
		    {
			 flag = 1;
			 break;
		    }
		    q.push(v);
	       }
	  }
	  if (flag) break;
     }
     if (d[(1<<n)-1] == 1e9)
     {
	  cout << "NO";
	  return 0;
     }
     cout << "YES" << "\n" << d[(1<<n)-1] << "\n";
     u = (1<<n)-1;
     if (n > 2 and d[u] != 2*n-4)
     {
	  while (true) {}
     }
     while (u != 0)
     {
	  for(auto p: B[u])
	  {
	       v = p.F;
	       w = p.S;
	       if (d[v] == d[u]-1)
	       {
		    cout << w << ' ';
		    u = v;
		    break;
	       }
	  }
     }
     return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 8
• Subtask 3: 0 / 80