oj.uz

Submission #338423

# Submission time Handle Problem Language Result Execution time Memory
338423 2020-12-23T05:53:50 Z tengiz05 Biochips (IZhO12_biochips) C++17
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool ckmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool ckmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int a[N], n, m, k;
int p[N];
void solve(int test_case){
	int i, j;
	cin >> n >> k;
	for(i=1;i<=n;i++){
		cin >> p[i] >> a[i];
	}
	int ans = -1;
	for(int mask = 0; mask < (1<<n); mask++){
		if(__builtin_popcount(mask) != k)continue;
		vector<int> v;
		for(i=0;i<n;i++){
			if(mask & (1<<i))v.pb(i+1);
		}
		assert(v.size() == k);
		vector<int> used(n+1);
		for(auto x : v)used[x] = 1;
		bool is = true;
		int sum = 0;
		for(auto x : v){
			sum += a[x];
			while(p[x] != 0){
				x = p[x];
				if(used[x])is = false;
			}
		}
		if(is)ckmax(ans,sum);
	}
	cout << ans << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from biochips.cpp:1:
biochips.cpp: In function 'void solve(long long int)':
biochips.cpp:31:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   31 |   assert(v.size() == k);
      |          ~~~~~~~~~^~~~
biochips.cpp:19:9: warning: unused variable 'j' [-Wunused-variable]
   19 |  int i, j;
      |         ^

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -