/*
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
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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
