oj.uz

Submission #698622

# Submission time Handle Problem Language Result Execution time Memory
698622 2023-02-14T05:37:54 Z cig32 Newspapers (CEOI21_newspapers) C++17
0 / 100
 495 ms 524288 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }

vector<int> adj[1029];
int state[(1 << 20)];
bool vis[(1 << 20)];
pair<int, int> pv[(1 << 20)];
vector<pair<int, int> > trans[(1 << 20)];
int msk[21];
void solve(int tc) {
  int n, m; cin >> n >> m;
  for(int i=0; i<(1<<n)-1; i++) state[i] = 1e9;
  state[(1<<n)-1] = 0;
  for(int i=0; i<m; i++) {
    int u, v; cin >> u >> v;
    u--, v--;
    msk[u] |= (1 << v);
    msk[v] |= (1 << u);
  }

  for(int i=0; i<(1<<n); i++) {
    int nxt= 0;
    for(int j=0; j<n; j++) {
      if(i & (1<<j)) {
        nxt |= msk[j];
      }
    }
    for(int j=0; j<n; j++) {
      int rl = nxt | (1<<j);
      rl ^= (1<<j);
      trans[i].push_back({rl, j});
    }
  }
  queue<int> q;
  q.push((1<<n) - 1);
  while(q.size()) {
    int f=q.front(); q.pop();
    if(!vis[f]) {
      vis[f] = 1;
      for(pair<int, int> x: trans[f]) {
        if(!vis[x.first] && state[x.first]>state[f] + 1) {
          state[x.first] = state[f] + 1; 
          pv[x.first] = {f, x.second};
          q.push(x.first);
        }
      }
    }
  }
  cout << (state[0] == 1e9 ? "NO\n" : "YES\n");
  int cur = 0;
  stack<int> stk;
  while(cur != (1<<n) - 1) {
    stk.push(pv[cur].second + 1);
    cur = pv[cur].first;
  }
  cout << stk.size() << "\n";
  while(stk.size()) {
    int ss=stk.top(); stk.pop();
    cout << ss;
    if(stk.size()) cout << " ";
    else cout << "\n";
  }
  

}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24944 KB Output is correct
2 Correct 16 ms 25044 KB Output is correct
3 Correct 13 ms 24980 KB Output is correct
4 Correct 13 ms 24980 KB Output is correct
5 Correct 13 ms 24980 KB Output is correct
6 Correct 14 ms 24980 KB Output is correct
7 Runtime error 495 ms 524288 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24916 KB Output is correct
2 Correct 16 ms 24976 KB Output is correct
3 Correct 13 ms 24916 KB Output is correct
4 Correct 14 ms 24912 KB Output is correct
5 Correct 13 ms 24916 KB Output is correct
6 Correct 13 ms 24936 KB Output is correct
7 Correct 14 ms 24936 KB Output is correct
8 Correct 14 ms 24912 KB Output is correct
9 Correct 14 ms 25044 KB Output is correct
10 Correct 14 ms 25172 KB Output is correct
11 Runtime error 37 ms 51380 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24944 KB Output is correct
2 Correct 16 ms 25044 KB Output is correct
3 Correct 13 ms 24980 KB Output is correct
4 Correct 13 ms 24980 KB Output is correct
5 Correct 13 ms 24980 KB Output is correct
6 Correct 14 ms 24980 KB Output is correct
7 Runtime error 495 ms 524288 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -