Submission #386594

#	Time	Username	Problem	Language	Result	Execution time	Memory
386594		talant117408	Biochips (IZhO12_biochips)	C++17	0 / 100	4 ms	5100 KiB

biochips

/*
    Code written by Talant I.D.
*/
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
 
const int mod = 998244353;
 
ll mode(ll a) {
    a %= mod;
    if (a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b) {
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b) {
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b) {
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}
 
void usaco(string s) {
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int N = 2e5+7;
int up[N][20], tin[N], tout[N], timer, memory[N];
vector <int> graph[N];

void dfs(int v, int p) {
	tin[v] = ++timer;
	up[v][0] = p;
	for (int i = 1; i < 20; i++) up[v][i] = up[up[v][i-1]][i-1];
	for (auto to : graph[v]) {
		if (to == p) continue;
		dfs(to, v);
	}
	tout[v] = ++timer;
}

bool upper(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
	if (upper(a, b)) return a;
	if (upper(b, a)) return b;
	for (int i = 19; i >= 0; i--) {
		if (!upper(up[a][i], b)) {
			a = up[a][i];
		}
	}
	return up[a][0];
}

int main() {
    do_not_disturb
    //~ usaco("marathon");
    
    int n, m;
    cin >> n >> m;
    if (n < 21 && m < 11) {
		int root = -1;
		for (int i = 1; i <= n; i++) {
			int x;
			cin >> x >> memory[i];
			if (x) graph[x].pb(i);
			else root = i;
		}
		
		dfs(root, root);
		
		int ans = 0;
		for (int mask = 1; mask < (1<<n); mask++) {
			if (__builtin_popcount(mask) != m) continue;
			vector <int> vertices;
			for (int i = 0; i < n; i++) {
				if (mask & (1<<i)) vertices.pb(i+1);
			}
			int flag = 1;
			for (int i = 0; i < m; i++) {
				for (int j = i+1; j < m; j++) {
					if (upper(vertices[i], vertices[j]) || upper(vertices[j], vertices[i])) {
						flag = 0;
					}
				}
			}
			if (flag) {
				int res = 0;
				for (auto to : vertices) res += memory[to];
				ans = max(ans, res);
			}
		}
		cout << ans;
	}
    
    return 0;
}

Compilation message (stderr)

biochips.cpp: In function 'void usaco(std::string)':
biochips.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
biochips.cpp:58:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   58 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100