Submission #19103570

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
void chmin(int& a, int b){ if(a > b) a = b; }

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> g(N);
    while(M--){
        int A, B;
        cin >> A >> B;
        A--; B--;
        g[A] |= 1 << B;
        g[B] |= 1 << A;
    }
    vector dp(1 << N, INF);
    dp[0] = 1;
    for(int i = 0; i < N; i++) for(int j = 0; j < 1 << N; j++){
        if(dp[j] == 1 && (g[i] & j) == j) dp[j | 1 << i] = 1;
    }
    for(int i = 1; i < 1 << N; i++) for(int j = i; --j &= i; ) {
        chmin(dp[i], dp[i ^ j] + dp[j]);
    }
    cout << dp.back() << endl;
}

Submission Info

Submission Time
Task F - Close Group
User tatyam
Language C++ (GCC 9.2.1)
Score 600
Code Size 636 Byte
Status AC
Exec Time 474 ms
Memory 4292 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status AC
AC × 44
Set Name Test Cases
Sample
All 01_sample.txt, 02_sample.txt, 03_sample.txt, 04_sample.txt, 05_tiny.txt, 06_tiny.txt, 07_tiny.txt, 08_tiny.txt, 09_tiny.txt, 10_tiny.txt, 11_tiny.txt, 12_small.txt, 13_small.txt, 14_small.txt, 15_small.txt, 16_small.txt, 17_small.txt, 18_small.txt, 19_small.txt, 20_small.txt, 21_small.txt, 22_small.txt, 23_small.txt, 24_small.txt, 25_small.txt, 26_small.txt, 27_large.txt, 28_large.txt, 29_large.txt, 30_large.txt, 31_large.txt, 32_large.txt, 33_large.txt, 34_large.txt, 35_large.txt, 36_large.txt, 37_large.txt, 38_large.txt, 39_large.txt, 40_large.txt, 41_large.txt, 42_max.txt, 43_max.txt, 44_max.txt
Case Name Status Exec Time Memory
01_sample.txt AC 8 ms 3436 KiB
02_sample.txt AC 2 ms 3528 KiB
03_sample.txt AC 2 ms 3460 KiB
04_sample.txt AC 470 ms 4112 KiB
05_tiny.txt AC 4 ms 3528 KiB
06_tiny.txt AC 2 ms 3384 KiB
07_tiny.txt AC 2 ms 3440 KiB
08_tiny.txt AC 2 ms 3388 KiB
09_tiny.txt AC 1 ms 3436 KiB
10_tiny.txt AC 2 ms 3412 KiB
11_tiny.txt AC 2 ms 3572 KiB
12_small.txt AC 4 ms 3604 KiB
13_small.txt AC 2 ms 3440 KiB
14_small.txt AC 2 ms 3384 KiB
15_small.txt AC 2 ms 3532 KiB
16_small.txt AC 2 ms 3456 KiB
17_small.txt AC 2 ms 3556 KiB
18_small.txt AC 2 ms 3380 KiB
19_small.txt AC 2 ms 3536 KiB
20_small.txt AC 2 ms 3452 KiB
21_small.txt AC 2 ms 3504 KiB
22_small.txt AC 2 ms 3400 KiB
23_small.txt AC 3 ms 3572 KiB
24_small.txt AC 2 ms 3460 KiB
25_small.txt AC 2 ms 3556 KiB
26_small.txt AC 1 ms 3444 KiB
27_large.txt AC 472 ms 4112 KiB
28_large.txt AC 29 ms 3376 KiB
29_large.txt AC 62 ms 3528 KiB
30_large.txt AC 8 ms 3488 KiB
31_large.txt AC 169 ms 3588 KiB
32_large.txt AC 466 ms 4112 KiB
33_large.txt AC 465 ms 4120 KiB
34_large.txt AC 472 ms 4292 KiB
35_large.txt AC 474 ms 4124 KiB
36_large.txt AC 468 ms 4204 KiB
37_large.txt AC 166 ms 3704 KiB
38_large.txt AC 3 ms 3456 KiB
39_large.txt AC 2 ms 3612 KiB
40_large.txt AC 2 ms 3560 KiB
41_large.txt AC 4 ms 3588 KiB
42_max.txt AC 461 ms 4192 KiB
43_max.txt AC 460 ms 4204 KiB
44_max.txt AC 470 ms 4108 KiB