oj.uz

Submission #698620

# Submission time Handle Problem Language Result Execution time Memory
698620 2023-02-14T05:33:04 Z cig32 Newspapers (CEOI21_newspapers) C++17
6 / 100
 435 ms 312944 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)];
vector<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);
    }
  }
  queue<int> q;
  q.push((1<<n) - 1);
  while(q.size()) {
    int f=q.front(); q.pop();
    if(!vis[f]) {
      vis[f] = 1;
      for(int x: trans[f]) {
        if(!vis[x] && state[x]>state[f] + 1) {
          state[x] = state[f] + 1; q.push(x);
        }
      }
    }
  }
  cout << (state[0] == 1e9 ? "NO\n" : "YES\n");
  if(state[0] != 1e9) {
    cout << "1\n";
    cout << "1\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
6.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24916 KB Output is correct
2 Partially correct 13 ms 24916 KB Failed to provide a successful strategy.
3 Partially correct 13 ms 24916 KB Failed to provide a successful strategy.
4 Partially correct 13 ms 24984 KB Failed to provide a successful strategy.
5 Partially correct 13 ms 24916 KB Failed to provide a successful strategy.
6 Partially correct 13 ms 24976 KB Failed to provide a successful strategy.
7 Correct 12 ms 24916 KB Output is correct
8 Partially correct 14 ms 24984 KB Failed to provide a successful strategy.
9 Correct 14 ms 25044 KB Output is correct
10 Partially correct 13 ms 24976 KB Failed to provide a successful strategy.
11 Partially correct 13 ms 24916 KB Failed to provide a successful strategy.
12 Partially correct 13 ms 24916 KB Failed to provide a successful strategy.
13 Partially correct 13 ms 24932 KB Failed to provide a successful strategy.
14 Partially correct 13 ms 24884 KB Failed to provide a successful strategy.
15 Partially correct 14 ms 25044 KB Failed to provide a successful strategy.
16 Partially correct 16 ms 25044 KB Failed to provide a successful strategy.
17 Partially correct 14 ms 25104 KB Failed to provide a successful strategy.
18 Partially correct 13 ms 25116 KB Failed to provide a successful strategy.
19 Partially correct 13 ms 25200 KB Failed to provide a successful strategy.
20 Partially correct 16 ms 25172 KB Failed to provide a successful strategy.
21 Partially correct 14 ms 25232 KB Failed to provide a successful strategy.
22 Partially correct 16 ms 25172 KB Failed to provide a successful strategy.
23 Partially correct 15 ms 25516 KB Failed to provide a successful strategy.
24 Partially correct 17 ms 25492 KB Failed to provide a successful strategy.
25 Partially correct 15 ms 25568 KB Failed to provide a successful strategy.
26 Partially correct 14 ms 25556 KB Failed to provide a successful strategy.
27 Partially correct 20 ms 26208 KB Failed to provide a successful strategy.
28 Partially correct 15 ms 26216 KB Failed to provide a successful strategy.
29 Correct 15 ms 26208 KB Output is correct
30 Partially correct 15 ms 26212 KB Failed to provide a successful strategy.
31 Partially correct 17 ms 27352 KB Failed to provide a successful strategy.
32 Partially correct 20 ms 27412 KB Failed to provide a successful strategy.
33 Partially correct 18 ms 27448 KB Failed to provide a successful strategy.
34 Correct 18 ms 27408 KB Output is correct
35 Partially correct 22 ms 29788 KB Failed to provide a successful strategy.
36 Partially correct 22 ms 29840 KB Failed to provide a successful strategy.
37 Partially correct 22 ms 29796 KB Failed to provide a successful strategy.
38 Partially correct 22 ms 29892 KB Failed to provide a successful strategy.
39 Partially correct 34 ms 34764 KB Failed to provide a successful strategy.
40 Partially correct 32 ms 34752 KB Failed to provide a successful strategy.
41 Partially correct 32 ms 34772 KB Failed to provide a successful strategy.
42 Partially correct 35 ms 34668 KB Failed to provide a successful strategy.
43 Partially correct 69 ms 60944 KB Failed to provide a successful strategy.
44 Partially correct 62 ms 60912 KB Failed to provide a successful strategy.
45 Correct 61 ms 60956 KB Output is correct
46 Correct 61 ms 61008 KB Output is correct
47 Correct 142 ms 96964 KB Output is correct
48 Partially correct 118 ms 97024 KB Failed to provide a successful strategy.
49 Correct 111 ms 96980 KB Output is correct
50 Correct 115 ms 97032 KB Output is correct
51 Partially correct 274 ms 169112 KB Failed to provide a successful strategy.
52 Correct 208 ms 168788 KB Output is correct
53 Correct 208 ms 168964 KB Output is correct
54 Partially correct 221 ms 169012 KB Failed to provide a successful strategy.
55 Correct 408 ms 312780 KB Output is correct
56 Correct 425 ms 312600 KB Output is correct
57 Correct 412 ms 312944 KB Output is correct
58 Correct 417 ms 312836 KB Output is correct
59 Correct 405 ms 312296 KB Output is correct
60 Correct 406 ms 312272 KB Output is correct
61 Correct 435 ms 312268 KB Output is correct
62 Correct 416 ms 312276 KB Output is correct
63 Correct 410 ms 312264 KB Output is correct
64 Correct 405 ms 312276 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24916 KB Output is correct
2 Partially correct 15 ms 24984 KB Failed to provide a successful strategy.
3 Partially correct 14 ms 24916 KB Failed to provide a successful strategy.
4 Partially correct 15 ms 24916 KB Failed to provide a successful strategy.
5 Partially correct 13 ms 24916 KB Failed to provide a successful strategy.
6 Partially correct 14 ms 24944 KB Failed to provide a successful strategy.
7 Partially correct 14 ms 24916 KB Failed to provide a successful strategy.
8 Partially correct 13 ms 24984 KB Failed to provide a successful strategy.
9 Partially correct 14 ms 24996 KB Failed to provide a successful strategy.
10 Partially correct 14 ms 25116 KB Failed to provide a successful strategy.
11 Runtime error 34 ms 51452 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 13 ms 24916 KB Output is correct
2 Partially correct 13 ms 24916 KB Failed to provide a successful strategy.
3 Partially correct 13 ms 24916 KB Failed to provide a successful strategy.
4 Partially correct 13 ms 24984 KB Failed to provide a successful strategy.
5 Partially correct 13 ms 24916 KB Failed to provide a successful strategy.
6 Partially correct 13 ms 24976 KB Failed to provide a successful strategy.
7 Correct 12 ms 24916 KB Output is correct
8 Partially correct 14 ms 24984 KB Failed to provide a successful strategy.
9 Correct 14 ms 25044 KB Output is correct
10 Partially correct 13 ms 24976 KB Failed to provide a successful strategy.
11 Partially correct 13 ms 24916 KB Failed to provide a successful strategy.
12 Partially correct 13 ms 24916 KB Failed to provide a successful strategy.
13 Partially correct 13 ms 24932 KB Failed to provide a successful strategy.
14 Partially correct 13 ms 24884 KB Failed to provide a successful strategy.
15 Partially correct 14 ms 25044 KB Failed to provide a successful strategy.
16 Partially correct 16 ms 25044 KB Failed to provide a successful strategy.
17 Partially correct 14 ms 25104 KB Failed to provide a successful strategy.
18 Partially correct 13 ms 25116 KB Failed to provide a successful strategy.
19 Partially correct 13 ms 25200 KB Failed to provide a successful strategy.
20 Partially correct 16 ms 25172 KB Failed to provide a successful strategy.
21 Partially correct 14 ms 25232 KB Failed to provide a successful strategy.
22 Partially correct 16 ms 25172 KB Failed to provide a successful strategy.
23 Partially correct 15 ms 25516 KB Failed to provide a successful strategy.
24 Partially correct 17 ms 25492 KB Failed to provide a successful strategy.
25 Partially correct 15 ms 25568 KB Failed to provide a successful strategy.
26 Partially correct 14 ms 25556 KB Failed to provide a successful strategy.
27 Partially correct 20 ms 26208 KB Failed to provide a successful strategy.
28 Partially correct 15 ms 26216 KB Failed to provide a successful strategy.
29 Correct 15 ms 26208 KB Output is correct
30 Partially correct 15 ms 26212 KB Failed to provide a successful strategy.
31 Partially correct 17 ms 27352 KB Failed to provide a successful strategy.
32 Partially correct 20 ms 27412 KB Failed to provide a successful strategy.
33 Partially correct 18 ms 27448 KB Failed to provide a successful strategy.
34 Correct 18 ms 27408 KB Output is correct
35 Partially correct 22 ms 29788 KB Failed to provide a successful strategy.
36 Partially correct 22 ms 29840 KB Failed to provide a successful strategy.
37 Partially correct 22 ms 29796 KB Failed to provide a successful strategy.
38 Partially correct 22 ms 29892 KB Failed to provide a successful strategy.
39 Partially correct 34 ms 34764 KB Failed to provide a successful strategy.
40 Partially correct 32 ms 34752 KB Failed to provide a successful strategy.
41 Partially correct 32 ms 34772 KB Failed to provide a successful strategy.
42 Partially correct 35 ms 34668 KB Failed to provide a successful strategy.
43 Partially correct 69 ms 60944 KB Failed to provide a successful strategy.
44 Partially correct 62 ms 60912 KB Failed to provide a successful strategy.
45 Correct 61 ms 60956 KB Output is correct
46 Correct 61 ms 61008 KB Output is correct
47 Correct 142 ms 96964 KB Output is correct
48 Partially correct 118 ms 97024 KB Failed to provide a successful strategy.
49 Correct 111 ms 96980 KB Output is correct
50 Correct 115 ms 97032 KB Output is correct
51 Partially correct 274 ms 169112 KB Failed to provide a successful strategy.
52 Correct 208 ms 168788 KB Output is correct
53 Correct 208 ms 168964 KB Output is correct
54 Partially correct 221 ms 169012 KB Failed to provide a successful strategy.
55 Correct 408 ms 312780 KB Output is correct
56 Correct 425 ms 312600 KB Output is correct
57 Correct 412 ms 312944 KB Output is correct
58 Correct 417 ms 312836 KB Output is correct
59 Correct 405 ms 312296 KB Output is correct
60 Correct 406 ms 312272 KB Output is correct
61 Correct 435 ms 312268 KB Output is correct
62 Correct 416 ms 312276 KB Output is correct
63 Correct 410 ms 312264 KB Output is correct
64 Correct 405 ms 312276 KB Output is correct
65 Correct 14 ms 24916 KB Output is correct
66 Partially correct 15 ms 24984 KB Failed to provide a successful strategy.
67 Partially correct 14 ms 24916 KB Failed to provide a successful strategy.
68 Partially correct 13 ms 24980 KB Failed to provide a successful strategy.
69 Partially correct 14 ms 24916 KB Failed to provide a successful strategy.
70 Partially correct 14 ms 24916 KB Failed to provide a successful strategy.
71 Correct 14 ms 24916 KB Output is correct
72 Partially correct 13 ms 24996 KB Failed to provide a successful strategy.
73 Correct 14 ms 25044 KB Output is correct
74 Partially correct 14 ms 24972 KB Failed to provide a successful strategy.
75 Partially correct 14 ms 24916 KB Failed to provide a successful strategy.
76 Partially correct 13 ms 24916 KB Failed to provide a successful strategy.
77 Partially correct 14 ms 24916 KB Failed to provide a successful strategy.
78 Partially correct 15 ms 24872 KB Failed to provide a successful strategy.
79 Runtime error 44 ms 66992 KB Execution killed with signal 11
80 Halted 0 ms 0 KB -