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
Task G - Mixture Drug
User hornistyf
Language C++ (GCC 9.2.1)
Score 0
Code Size 1789 Byte
Status WA
Exec Time 76 ms
Memory 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
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.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