oj.uz

답안 #659570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
659570 2022-11-18T14:46:00 Z Vladth11 바이오칩 (IZhO12_biochips) C++14
0 / 100
 4 ms 4948 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const int base = 31;
const int NMAX = 200002;
const int INF = 1e9;
const int VMAX = 501;
const int nrbits = 17;
const int MOD = 1000000007;

int dp[NMAX][VMAX];
vector <int> g[NMAX];
int timp[NMAX];
int stamp;
int v[NMAX];
int m;
int root;

void maxSelf(int &x, int val){
    x = max(x, val);
}

void DFS(int node, int p){
    timp[node] = stamp;
    for(auto x : g[node]){
        if(x == p) continue;
        DFS(x, node);
    }
    ++stamp;
    for(int i = 0; i <= m; i++){
        dp[stamp][i] = dp[stamp - 1][i];
    }
    for(int i = 1; i <= m; i++){
        maxSelf(dp[stamp][i], dp[timp[node]][i - 1] + v[node]);
    }
}

int main() {
    ifstream cin("d.in");
    ofstream cout("d.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n >> m;
    for(int i = 0; i <= m; i++)
        dp[0][i] = -INF;
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++){
        int p;
        cin >> p >> v[i];
        if(p == 0){
            root = i;
        }else{
            g[i].push_back(p);
            g[p].push_back(i);
        }
    }
    DFS(root, 0);
    cout << dp[stamp][m];
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Incorrect 2 ms 4948 KB Output isn't correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Incorrect 2 ms 4948 KB Output isn't correct
6 Incorrect 2 ms 4948 KB Output isn't correct
7 Incorrect 2 ms 4948 KB Output isn't correct
8 Incorrect 3 ms 4948 KB Output isn't correct
9 Incorrect 4 ms 4948 KB Output isn't correct
10 Incorrect 3 ms 4948 KB Output isn't correct