Contest Duration: - (local time) (180 minutes)

Submission #19108169

Source Code Expand

Copy
```//q107.cpp
//Sat Jan  2 09:27:51 2021

#include <bits/stdc++.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007
#define rep(i,n) for (int i=0;i<(n);++i)

using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
int n,m;
cin >> n >> m;

vector<int> p[n];
rep(i,m){
int a,b;
cin >> a >> b;
a--;b--;
p[a].push_back(b);
p[b].push_back(a);
}

int n1 = (n+1)/2;
int n2 = n/2;

bool ok1[1<<n1];
fill(ok1,ok1+(1<<n1),true);
rep(i,n1){
rep(j,p[i].size()){
if (p[i][j]<n1){
ok1[(1<<i)|(1<<p[i][j])] = false;
}
}
}
rep(i,1<<n1){
if (!ok1[i]){
rep(j,n1){
ok1[i|(1<<j)] = false;
}
}
}

int ok2[1<<n1];
ok2[0] = (1<<n2)-1;
rep(i,n1){
ok2[1<<i] = (1<<n2)-1;
rep(j,p[i].size()){
if (p[i][j]>=n1){
ok2[1<<i] = ok2[1<<i]^(1<<(p[i][j]-n1));
}
}
}
rep(i,1<<n1){
rep(j,n1){
ok2[i|(1<<j)] = ok2[i]&ok2[1<<j];
}
}

bool ok3[1<<n2];
fill(ok3,ok3+(1<<n2),true);
for (int i=n1;i<n;i++){
rep(j,p[i].size()){
if (p[i][j]>=n1){
ok3[(1<<(i-n1))|(1<<(p[i][j]-n1))] = false;
}
}
}
rep(i,1<<n2){
if (!ok3[i]){
rep(j,n2){
ok3[i|(1<<j)] = false;
}
}
}

int ok3count[1<<n2];
fill(ok3count,ok3count+(1<<n2),0);
rep(i,1<<n2){
if (ok3[i]){
ok3count[i] = bitset<32>(i).count();
// int cnt = 0;
// rep(j,n2)if(i>>j&1)cnt++;
// ok3count[i] = cnt;
}
}

int ans = 0;
rep(i,1<<n1){
if (!ok1[i])continue;
int cnt = bitset<32>(i).count();
// int cnt = 0;
// rep(j,n1)if(i>>j&1)cnt++;
ans = max(ans,cnt+ok3count[ok2[i]]);
}

cout << ans << endl;
// rep(i,1<<n1){
// 	cout << i << " " << ok1[i] << " " << ok2[i] << endl;
// }
}```

#### Submission Info

Submission Time 2021-01-02 12:41:12+0900 G - Mixture Drug hornistyf C++ (GCC 9.2.1) 0 1789 Byte WA 76 ms 13848 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:8:32: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
8 | #define rep(i,n) for (int i=0;i<(n);++i)
|                                ^
./Main.cpp:33:3: note: in expansion of macro ‘rep’
33 |   rep(j,p[i].size()){
|   ^~~
./Main.cpp:8:32: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
8 | #define rep(i,n) for (int i=0;i<(n);++i)
|                                ^
./Main.cpp:51:3: note: in expansion of macro ‘rep’
51 |   rep(j,p[i].size()){
|   ^~~
./Main.cpp:8:32: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
8 | #define rep(i,n) for (int i=0;i<(n);++i)
|                                ^
./Main.cpp:66:3: note: in expansion of macro ‘rep’
66 |   rep(j,p[i].size()){
|   ^~~
```

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
 AC × 2 WA × 1
 AC × 34 WA × 17
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
sample_01.txt AC 9 ms 3380 KB
sample_02.txt AC 2 ms 3524 KB
sample_03.txt WA 2 ms 3380 KB
subtask_1_1.txt AC 2 ms 3432 KB
subtask_1_10.txt WA 71 ms 13756 KB
subtask_1_11.txt WA 3 ms 3568 KB
subtask_1_12.txt WA 76 ms 13676 KB
subtask_1_13.txt AC 52 ms 11140 KB
subtask_1_14.txt AC 56 ms 13808 KB
subtask_1_15.txt AC 3 ms 3584 KB
subtask_1_16.txt AC 72 ms 13612 KB
subtask_1_17.txt AC 71 ms 13756 KB
subtask_1_18.txt AC 69 ms 13836 KB
subtask_1_19.txt AC 3 ms 3488 KB
subtask_1_2.txt AC 55 ms 13612 KB
subtask_1_20.txt AC 67 ms 13836 KB
subtask_1_21.txt AC 71 ms 13816 KB
subtask_1_22.txt AC 71 ms 13704 KB
subtask_1_23.txt AC 2 ms 3520 KB
subtask_1_24.txt AC 10 ms 4096 KB
subtask_1_25.txt WA 72 ms 13756 KB
subtask_1_26.txt WA 71 ms 13684 KB
subtask_1_27.txt WA 71 ms 13808 KB
subtask_1_28.txt WA 72 ms 13824 KB
subtask_1_29.txt WA 71 ms 13820 KB
subtask_1_3.txt AC 17 ms 5500 KB
subtask_1_30.txt AC 2 ms 3400 KB
subtask_1_31.txt WA 3 ms 3604 KB
subtask_1_32.txt AC 2 ms 3556 KB
subtask_1_33.txt AC 9 ms 3864 KB
subtask_1_34.txt WA 65 ms 13752 KB
subtask_1_35.txt AC 72 ms 13736 KB
subtask_1_36.txt WA 72 ms 13704 KB
subtask_1_37.txt AC 69 ms 13776 KB
subtask_1_38.txt AC 70 ms 13836 KB
subtask_1_39.txt AC 72 ms 13660 KB
subtask_1_4.txt AC 70 ms 13716 KB
subtask_1_40.txt AC 72 ms 13848 KB
subtask_1_41.txt AC 71 ms 13708 KB
subtask_1_42.txt AC 70 ms 13620 KB
subtask_1_43.txt AC 69 ms 13704 KB
subtask_1_44.txt AC 68 ms 13624 KB
subtask_1_45.txt AC 66 ms 13700 KB
subtask_1_46.txt AC 58 ms 13752 KB
subtask_1_47.txt AC 70 ms 13768 KB
subtask_1_48.txt AC 68 ms 13760 KB
subtask_1_5.txt WA 24 ms 6144 KB
subtask_1_6.txt WA 68 ms 13812 KB
subtask_1_7.txt WA 37 ms 7300 KB
subtask_1_8.txt WA 70 ms 13824 KB
subtask_1_9.txt WA 38 ms 8576 KB