제출 #1185999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185999		gyg	Tree (IOI24_tree)	C++20	10 / 100	2096 ms	22944 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array 
#define vec vector 
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 2e5 + 5;

int n;
arr<vec<int>, N> ch;
arr<int, N> wg;

void init(vec<sig> _pr, vec<sig> _wg) {
    n = _pr.size();
    for (int u = 1; u <= n; u++)
        ch[_pr[u - 1] + 1].push_back(u);
    for (int u = 1; u <= n; u++)
        wg[u] = _wg[u - 1];
}

arr<int, N> vl;
int dfs(int l, int r, int u = 1) {
    if (ch[u].empty()) { vl[u] = l; return l; }
    
    int sm = 0;
    for (int v : ch[u]) 
        sm += dfs(l, r, v);
    
    if (sm > r) {
        vl[u] = -(sm - r);
        sm = r;
    }
    return sm;
}

int query(sig l, sig r) {
    vl.fill(0);
    dfs(l, r);

    int ans = 0;
    for (int u = 1; u <= n; u++) ans += abs(vl[u]) * wg[u];
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 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