oj.uz

Submission #464726

# Submission time Handle Problem Language Result Execution time Memory
464726 2021-08-13T20:43:59 Z aryan12 Biochips (IZhO12_biochips) C++17
0 / 100
 314 ms 524292 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5324 KB Output is correct
4 Correct 21 ms 40524 KB Output is correct
5 Correct 23 ms 44876 KB Output is correct
6 Correct 28 ms 44936 KB Output is correct
7 Runtime error 314 ms 524292 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -