oj.uz

Submission #955448

# Submission time Handle Problem Language Result Execution time Memory
955448 2024-03-30T13:06:47 Z yoav_s Newspapers (CEOI21_newspapers) C++17
6 / 100
 475 ms 279492 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll,ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()

const ll INF = 1e18;
const ll mod = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll N, M;
    cin >> N >> M;
    vv graph(N);
    for (ll i=  0; i < M; i++)
    {
        ll a, b;
        cin >> a >> b;
        graph[a-1].pb(b-1);
        graph[b-1].pb(a-1);
    }
    v next((1ll << N));
    for (ll i=  0; i < (1ll << N); i++)
    {
        for (ll j = 0; j < N; j++)
        {
            if (i & (1 << j))
            {
                for (ll x : graph[j]) next[i] |= (1 << x);
            }
        }
    }
    vvp stateGraph((1ll << N));
    for (ll i = 0; i < (1 << N); i++)
    {
        for (ll j = 0; j < N; j++)
        {
            if (i & (1 << j))
                stateGraph[i].eb(next[i ^ (1 << j)], j);
        }
    }
    vb visited((1 << N), false);
    ll start = (1 << N) - 1; ll end = 0;
    stack<ll> dfs;
    dfs.push(start);
    while (!dfs.empty())
    {
        auto top = dfs.top(); dfs.pop();
        if (visited[top]) continue; visited[top] = true;
        for (auto x : stateGraph[top]) dfs.push(x.f);
    }
    if (visited[end]) cout << "YES\n1\n1\n";
    else cout << "NO\n";
    return 0;
}

Compilation message

newspapers.cpp: In function 'int main()':
newspapers.cpp:70:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   70 |         if (visited[top]) continue; visited[top] = true;
      |         ^~
newspapers.cpp:70:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   70 |         if (visited[top]) continue; visited[top] = true;
      |                                     ^~~~~~~

Subtask #1
6.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
3 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
4 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
5 Partially correct 1 ms 348 KB Failed to provide a successful strategy.
6 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
7 Correct 0 ms 348 KB Output is correct
8 Partially correct 1 ms 348 KB Failed to provide a successful strategy.
9 Correct 1 ms 604 KB Output is correct
10 Partially correct 0 ms 344 KB Failed to provide a successful strategy.
11 Partially correct 1 ms 348 KB Failed to provide a successful strategy.
12 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
13 Partially correct 1 ms 344 KB Failed to provide a successful strategy.
14 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
15 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
16 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
17 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
18 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
19 Partially correct 1 ms 712 KB Failed to provide a successful strategy.
20 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
21 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
22 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
23 Partially correct 1 ms 1116 KB Failed to provide a successful strategy.
24 Partially correct 1 ms 1116 KB Failed to provide a successful strategy.
25 Partially correct 1 ms 1116 KB Failed to provide a successful strategy.
26 Partially correct 1 ms 1112 KB Failed to provide a successful strategy.
27 Partially correct 3 ms 1884 KB Failed to provide a successful strategy.
28 Partially correct 3 ms 1884 KB Failed to provide a successful strategy.
29 Correct 3 ms 1884 KB Output is correct
30 Partially correct 3 ms 1884 KB Failed to provide a successful strategy.
31 Partially correct 5 ms 3500 KB Failed to provide a successful strategy.
32 Partially correct 6 ms 3416 KB Failed to provide a successful strategy.
33 Partially correct 5 ms 3420 KB Failed to provide a successful strategy.
34 Correct 5 ms 3420 KB Output is correct
35 Partially correct 12 ms 7260 KB Failed to provide a successful strategy.
36 Partially correct 13 ms 7004 KB Failed to provide a successful strategy.
37 Partially correct 10 ms 7120 KB Failed to provide a successful strategy.
38 Partially correct 11 ms 7000 KB Failed to provide a successful strategy.
39 Partially correct 22 ms 14672 KB Failed to provide a successful strategy.
40 Partially correct 22 ms 14796 KB Failed to provide a successful strategy.
41 Partially correct 22 ms 14676 KB Failed to provide a successful strategy.
42 Partially correct 22 ms 14684 KB Failed to provide a successful strategy.
43 Partially correct 56 ms 30924 KB Failed to provide a successful strategy.
44 Partially correct 45 ms 30920 KB Failed to provide a successful strategy.
45 Correct 47 ms 30800 KB Output is correct
46 Correct 52 ms 31064 KB Output is correct
47 Correct 91 ms 64756 KB Output is correct
48 Partially correct 93 ms 64740 KB Failed to provide a successful strategy.
49 Correct 94 ms 64848 KB Output is correct
50 Correct 103 ms 64692 KB Output is correct
51 Partially correct 183 ms 134736 KB Failed to provide a successful strategy.
52 Correct 183 ms 134872 KB Output is correct
53 Correct 184 ms 134736 KB Output is correct
54 Partially correct 195 ms 134932 KB Failed to provide a successful strategy.
55 Correct 468 ms 279196 KB Output is correct
56 Correct 389 ms 279248 KB Output is correct
57 Correct 377 ms 279492 KB Output is correct
58 Correct 370 ms 279232 KB Output is correct
59 Correct 468 ms 279360 KB Output is correct
60 Correct 420 ms 279200 KB Output is correct
61 Correct 409 ms 279304 KB Output is correct
62 Correct 400 ms 279376 KB Output is correct
63 Correct 452 ms 279256 KB Output is correct
64 Correct 475 ms 279328 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
3 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
4 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
5 Partially correct 1 ms 348 KB Failed to provide a successful strategy.
6 Partially correct 0 ms 344 KB Failed to provide a successful strategy.
7 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
8 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
9 Partially correct 1 ms 348 KB Failed to provide a successful strategy.
10 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
11 Runtime error 3 ms 600 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
3 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
4 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
5 Partially correct 1 ms 348 KB Failed to provide a successful strategy.
6 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
7 Correct 0 ms 348 KB Output is correct
8 Partially correct 1 ms 348 KB Failed to provide a successful strategy.
9 Correct 1 ms 604 KB Output is correct
10 Partially correct 0 ms 344 KB Failed to provide a successful strategy.
11 Partially correct 1 ms 348 KB Failed to provide a successful strategy.
12 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
13 Partially correct 1 ms 344 KB Failed to provide a successful strategy.
14 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
15 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
16 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
17 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
18 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
19 Partially correct 1 ms 712 KB Failed to provide a successful strategy.
20 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
21 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
22 Partially correct 1 ms 604 KB Failed to provide a successful strategy.
23 Partially correct 1 ms 1116 KB Failed to provide a successful strategy.
24 Partially correct 1 ms 1116 KB Failed to provide a successful strategy.
25 Partially correct 1 ms 1116 KB Failed to provide a successful strategy.
26 Partially correct 1 ms 1112 KB Failed to provide a successful strategy.
27 Partially correct 3 ms 1884 KB Failed to provide a successful strategy.
28 Partially correct 3 ms 1884 KB Failed to provide a successful strategy.
29 Correct 3 ms 1884 KB Output is correct
30 Partially correct 3 ms 1884 KB Failed to provide a successful strategy.
31 Partially correct 5 ms 3500 KB Failed to provide a successful strategy.
32 Partially correct 6 ms 3416 KB Failed to provide a successful strategy.
33 Partially correct 5 ms 3420 KB Failed to provide a successful strategy.
34 Correct 5 ms 3420 KB Output is correct
35 Partially correct 12 ms 7260 KB Failed to provide a successful strategy.
36 Partially correct 13 ms 7004 KB Failed to provide a successful strategy.
37 Partially correct 10 ms 7120 KB Failed to provide a successful strategy.
38 Partially correct 11 ms 7000 KB Failed to provide a successful strategy.
39 Partially correct 22 ms 14672 KB Failed to provide a successful strategy.
40 Partially correct 22 ms 14796 KB Failed to provide a successful strategy.
41 Partially correct 22 ms 14676 KB Failed to provide a successful strategy.
42 Partially correct 22 ms 14684 KB Failed to provide a successful strategy.
43 Partially correct 56 ms 30924 KB Failed to provide a successful strategy.
44 Partially correct 45 ms 30920 KB Failed to provide a successful strategy.
45 Correct 47 ms 30800 KB Output is correct
46 Correct 52 ms 31064 KB Output is correct
47 Correct 91 ms 64756 KB Output is correct
48 Partially correct 93 ms 64740 KB Failed to provide a successful strategy.
49 Correct 94 ms 64848 KB Output is correct
50 Correct 103 ms 64692 KB Output is correct
51 Partially correct 183 ms 134736 KB Failed to provide a successful strategy.
52 Correct 183 ms 134872 KB Output is correct
53 Correct 184 ms 134736 KB Output is correct
54 Partially correct 195 ms 134932 KB Failed to provide a successful strategy.
55 Correct 468 ms 279196 KB Output is correct
56 Correct 389 ms 279248 KB Output is correct
57 Correct 377 ms 279492 KB Output is correct
58 Correct 370 ms 279232 KB Output is correct
59 Correct 468 ms 279360 KB Output is correct
60 Correct 420 ms 279200 KB Output is correct
61 Correct 409 ms 279304 KB Output is correct
62 Correct 400 ms 279376 KB Output is correct
63 Correct 452 ms 279256 KB Output is correct
64 Correct 475 ms 279328 KB Output is correct
65 Correct 1 ms 344 KB Output is correct
66 Partially correct 0 ms 344 KB Failed to provide a successful strategy.
67 Partially correct 1 ms 344 KB Failed to provide a successful strategy.
68 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
69 Partially correct 1 ms 348 KB Failed to provide a successful strategy.
70 Partially correct 0 ms 344 KB Failed to provide a successful strategy.
71 Correct 0 ms 348 KB Output is correct
72 Partially correct 1 ms 348 KB Failed to provide a successful strategy.
73 Correct 1 ms 604 KB Output is correct
74 Partially correct 1 ms 348 KB Failed to provide a successful strategy.
75 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
76 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
77 Partially correct 1 ms 348 KB Failed to provide a successful strategy.
78 Partially correct 0 ms 348 KB Failed to provide a successful strategy.
79 Runtime error 2 ms 604 KB Execution killed with signal 6
80 Halted 0 ms 0 KB -