oj.uz

Submission #1097489

# Submission time Handle Problem Language Result Execution time Memory
1097489 2024-10-07T13:17:16 Z alexander707070 Newspapers (CEOI21_newspapers) C++14
0 / 100
 1000 ms 249044 KB 
#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;
 
int n,m,a,b;
vector<int> v[MAXN],to[1<<22];
bool li[1<<22];
int nei[MAXN];

bool dfs(int x,int y){
    if(x==y)return true;

    li[x]=true;
    for(int i:to[x]){
        if(!li[i] and dfs(i,y))return true;
    }

    return false;
}

int main(){

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        a--; b--;
        v[a].push_back(b);
        v[b].push_back(a);

        nei[a]|=(1<<b);
        nei[b]|=(1<<a);
    }

    for(int i=0;i<(1<<n);i++){
        for(int f=0;f<n;f++){
            int res=0;

            for(int t=0;t<n;t++){
                if(((1<<t)&i)>0){
                    res|=nei[t];
                }
            }
            
            if((res&(1<<f))>0)res^=(1<<f);

            to[i].push_back(res);
        }
    }

    if(dfs((1<<n)-1,0)){
        cout<<"YES\n";
        cout<<"1\n1\n";
    }else{
        cout<<"NO\n";
    }
 
    return 0;
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 103508 KB Output is correct
2 Partially correct 50 ms 103508 KB Failed to provide a successful strategy.
3 Partially correct 50 ms 103552 KB Failed to provide a successful strategy.
4 Partially correct 49 ms 103380 KB Failed to provide a successful strategy.
5 Partially correct 48 ms 103516 KB Failed to provide a successful strategy.
6 Partially correct 50 ms 103396 KB Failed to provide a successful strategy.
7 Correct 51 ms 103432 KB Output is correct
8 Partially correct 48 ms 103516 KB Failed to provide a successful strategy.
9 Correct 52 ms 103560 KB Output is correct
10 Partially correct 49 ms 103512 KB Failed to provide a successful strategy.
11 Partially correct 49 ms 103508 KB Failed to provide a successful strategy.
12 Partially correct 48 ms 103536 KB Failed to provide a successful strategy.
13 Partially correct 50 ms 103516 KB Failed to provide a successful strategy.
14 Partially correct 50 ms 103604 KB Failed to provide a successful strategy.
15 Partially correct 48 ms 103592 KB Failed to provide a successful strategy.
16 Partially correct 53 ms 103508 KB Failed to provide a successful strategy.
17 Partially correct 49 ms 103504 KB Failed to provide a successful strategy.
18 Partially correct 49 ms 103508 KB Failed to provide a successful strategy.
19 Partially correct 54 ms 103760 KB Failed to provide a successful strategy.
20 Partially correct 50 ms 103772 KB Failed to provide a successful strategy.
21 Partially correct 49 ms 103764 KB Failed to provide a successful strategy.
22 Partially correct 50 ms 103644 KB Failed to provide a successful strategy.
23 Partially correct 49 ms 103864 KB Failed to provide a successful strategy.
24 Partially correct 50 ms 103956 KB Failed to provide a successful strategy.
25 Partially correct 52 ms 103764 KB Failed to provide a successful strategy.
26 Partially correct 51 ms 103760 KB Failed to provide a successful strategy.
27 Partially correct 56 ms 104272 KB Failed to provide a successful strategy.
28 Partially correct 54 ms 104276 KB Failed to provide a successful strategy.
29 Correct 52 ms 104020 KB Output is correct
30 Partially correct 50 ms 104276 KB Failed to provide a successful strategy.
31 Partially correct 62 ms 104788 KB Failed to provide a successful strategy.
32 Partially correct 63 ms 104784 KB Failed to provide a successful strategy.
33 Partially correct 60 ms 104680 KB Failed to provide a successful strategy.
34 Correct 57 ms 104720 KB Output is correct
35 Partially correct 66 ms 106064 KB Failed to provide a successful strategy.
36 Partially correct 66 ms 106220 KB Failed to provide a successful strategy.
37 Partially correct 65 ms 106068 KB Failed to provide a successful strategy.
38 Partially correct 66 ms 106076 KB Failed to provide a successful strategy.
39 Partially correct 91 ms 108584 KB Failed to provide a successful strategy.
40 Partially correct 92 ms 108628 KB Failed to provide a successful strategy.
41 Partially correct 90 ms 108624 KB Failed to provide a successful strategy.
42 Partially correct 90 ms 108772 KB Failed to provide a successful strategy.
43 Partially correct 147 ms 122196 KB Failed to provide a successful strategy.
44 Partially correct 150 ms 122192 KB Failed to provide a successful strategy.
45 Correct 145 ms 122124 KB Output is correct
46 Correct 168 ms 121976 KB Output is correct
47 Correct 283 ms 140604 KB Output is correct
48 Partially correct 279 ms 140624 KB Failed to provide a successful strategy.
49 Correct 278 ms 140624 KB Output is correct
50 Correct 294 ms 140880 KB Output is correct
51 Partially correct 548 ms 177744 KB Failed to provide a successful strategy.
52 Correct 546 ms 177748 KB Output is correct
53 Correct 575 ms 177744 KB Output is correct
54 Partially correct 572 ms 177848 KB Failed to provide a successful strategy.
55 Execution timed out 1054 ms 249044 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 103508 KB Output is correct
2 Partially correct 49 ms 103504 KB Failed to provide a successful strategy.
3 Partially correct 50 ms 103512 KB Failed to provide a successful strategy.
4 Partially correct 52 ms 103508 KB Failed to provide a successful strategy.
5 Partially correct 49 ms 103508 KB Failed to provide a successful strategy.
6 Partially correct 52 ms 103528 KB Failed to provide a successful strategy.
7 Partially correct 49 ms 103508 KB Failed to provide a successful strategy.
8 Partially correct 49 ms 103512 KB Failed to provide a successful strategy.
9 Partially correct 50 ms 103496 KB Failed to provide a successful strategy.
10 Partially correct 51 ms 103504 KB Failed to provide a successful strategy.
11 Execution timed out 1041 ms 110068 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 103508 KB Output is correct
2 Partially correct 50 ms 103508 KB Failed to provide a successful strategy.
3 Partially correct 50 ms 103552 KB Failed to provide a successful strategy.
4 Partially correct 49 ms 103380 KB Failed to provide a successful strategy.
5 Partially correct 48 ms 103516 KB Failed to provide a successful strategy.
6 Partially correct 50 ms 103396 KB Failed to provide a successful strategy.
7 Correct 51 ms 103432 KB Output is correct
8 Partially correct 48 ms 103516 KB Failed to provide a successful strategy.
9 Correct 52 ms 103560 KB Output is correct
10 Partially correct 49 ms 103512 KB Failed to provide a successful strategy.
11 Partially correct 49 ms 103508 KB Failed to provide a successful strategy.
12 Partially correct 48 ms 103536 KB Failed to provide a successful strategy.
13 Partially correct 50 ms 103516 KB Failed to provide a successful strategy.
14 Partially correct 50 ms 103604 KB Failed to provide a successful strategy.
15 Partially correct 48 ms 103592 KB Failed to provide a successful strategy.
16 Partially correct 53 ms 103508 KB Failed to provide a successful strategy.
17 Partially correct 49 ms 103504 KB Failed to provide a successful strategy.
18 Partially correct 49 ms 103508 KB Failed to provide a successful strategy.
19 Partially correct 54 ms 103760 KB Failed to provide a successful strategy.
20 Partially correct 50 ms 103772 KB Failed to provide a successful strategy.
21 Partially correct 49 ms 103764 KB Failed to provide a successful strategy.
22 Partially correct 50 ms 103644 KB Failed to provide a successful strategy.
23 Partially correct 49 ms 103864 KB Failed to provide a successful strategy.
24 Partially correct 50 ms 103956 KB Failed to provide a successful strategy.
25 Partially correct 52 ms 103764 KB Failed to provide a successful strategy.
26 Partially correct 51 ms 103760 KB Failed to provide a successful strategy.
27 Partially correct 56 ms 104272 KB Failed to provide a successful strategy.
28 Partially correct 54 ms 104276 KB Failed to provide a successful strategy.
29 Correct 52 ms 104020 KB Output is correct
30 Partially correct 50 ms 104276 KB Failed to provide a successful strategy.
31 Partially correct 62 ms 104788 KB Failed to provide a successful strategy.
32 Partially correct 63 ms 104784 KB Failed to provide a successful strategy.
33 Partially correct 60 ms 104680 KB Failed to provide a successful strategy.
34 Correct 57 ms 104720 KB Output is correct
35 Partially correct 66 ms 106064 KB Failed to provide a successful strategy.
36 Partially correct 66 ms 106220 KB Failed to provide a successful strategy.
37 Partially correct 65 ms 106068 KB Failed to provide a successful strategy.
38 Partially correct 66 ms 106076 KB Failed to provide a successful strategy.
39 Partially correct 91 ms 108584 KB Failed to provide a successful strategy.
40 Partially correct 92 ms 108628 KB Failed to provide a successful strategy.
41 Partially correct 90 ms 108624 KB Failed to provide a successful strategy.
42 Partially correct 90 ms 108772 KB Failed to provide a successful strategy.
43 Partially correct 147 ms 122196 KB Failed to provide a successful strategy.
44 Partially correct 150 ms 122192 KB Failed to provide a successful strategy.
45 Correct 145 ms 122124 KB Output is correct
46 Correct 168 ms 121976 KB Output is correct
47 Correct 283 ms 140604 KB Output is correct
48 Partially correct 279 ms 140624 KB Failed to provide a successful strategy.
49 Correct 278 ms 140624 KB Output is correct
50 Correct 294 ms 140880 KB Output is correct
51 Partially correct 548 ms 177744 KB Failed to provide a successful strategy.
52 Correct 546 ms 177748 KB Output is correct
53 Correct 575 ms 177744 KB Output is correct
54 Partially correct 572 ms 177848 KB Failed to provide a successful strategy.
55 Execution timed out 1054 ms 249044 KB Time limit exceeded
56 Halted 0 ms 0 KB -