Submission #1232364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232364		bangan	트리 (IOI24_tree)	C++20	0 / 100	2088 ms	6724 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)

#define pb push_back

const int N = 2000 + 4;
const int INF = 1ll << 20;

int n;
vector<int> p, w;
vector<int> adj[N];

void init(std::vector<int> P, std::vector<int> W) {
    n = P.size();
    p = P;
    w = W;
    for (int i=1; i<n; i++) adj[p[i]].pb(i);
}   

int dp[N][N];
void dfs(int v, int l, int r) {
    for (int x=0; x<N; x++) dp[v][x]= INF;
    if (adj[v].empty()) {
        for (int x=l; x<=r; x++) dp[v][x] = w[v] * x;
        return;
    }
    dp[v][0] = 0;
    for (int u : adj[v]) {
        dfs(u, l, r);
        vector<int> old_dp;
        for (int x=0; x<N; x++) old_dp.pb(dp[v][x]);
        for (int x=0; x<N; x++) dp[v][x]= INF;
        for (int x=0; x<N; x++) for (int y=0; y<N; y++) for (int z=l; z<=r; z++) {
            chmin(dp[v][x], old_dp[y] + dp[u][z] + abs(y+z - x) * w[v]);
        }
    }
}

long long query(int L, int R) {
    dfs(0, L, R);
    return *min_element(dp[0]+L, dp[0]+R+1);
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19