Submission #464726

#	Time	Username	Problem	Language	Result	Execution time	Memory
464726		aryan12	Biochips (IZhO12_biochips)	C++17	0 / 100	314 ms	524292 KiB

biochips

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5 + 5, M = 505;
vector<int> g[N];
int dp[N][M], val[N];
int tin[N], tim = 0;
int n, m;

void dfs(int node) {
    tin[node] = tim;
    for(int i = 0; i < g[node].size(); i++) {
        dfs(g[node][i]);
    }
    for(int i = 1; i <= m; i++) {
       // cout << "node = " << node << ", tim = " << tim << ", tin[node] = " << tin[node] << ", val[node] = " << val[node] << "\n";
        dp[tim + 1][i] = max(dp[tim][i], dp[tin[node]][i - 1] + val[node]);
    }
    tim++;
}

void Solve() {
    cin >> n >> m;
    int root = n + 1;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x >> val[i];
        if(x != 0) {
            g[x].push_back(i);
        }
        else {
            root = i;
        }
    }
    for(int i = 1; i <= m; i++) {
        dp[0][i] = -1e15;
    }
    dfs(root);
    /*for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }*/
    cout << dp[n][m] << "\n";
}

int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Compilation message (stderr)

biochips.cpp: In function 'void dfs(long long int)':
biochips.cpp:14:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i = 0; i < g[node].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100