제출 #1297656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1297656		m_a_d	Arboras (RMI20_arboras)	C++20	0 / 100	5094 ms	8656 KiB

arboras

#include <bits/stdc++.h>

using namespace std;

#define int long long

int fill_path_dp(vector<vector<int>> &adj, vector<int> &max_path, int w[], int curr) {
    if(max_path[curr]!=-1) return max_path[curr];
    if(adj[curr].size()==0) {
        max_path[curr]=0;
        return max_path[curr];
    }
    else {
        int value=0;
        for(auto &to:adj[curr]) {
            value=max(value, fill_path_dp(adj, max_path, w, to)+w[to]);
        }
        max_path[curr]=value;
        return max_path[curr];
    }
}

int update(int n, int increment, int p[], int w[], vector<int> &max_path) {
    w[n]+=increment;
    while(p[n]!=-1) {
        max_path[p[n]]=max(max_path[p[n]], max_path[n]+w[n]);
        n=p[n];
    }
}

int32_t main() {
    int n;
    cin >> n;
    int p[n], w[n];
    p[0]=-1;
    w[0]=0;
    vector<vector<int>> adj(n);
    for(int i=1; i<n; ++i) cin >> p[i];
    for(int i=1; i<n; ++i) cin >> w[i];
    for(int i=1; i<n; ++i) {
        adj[p[i]].push_back(i);
    }
    vector<int> max_path(n, -1);
    fill_path_dp(adj, max_path, w, 0);
    int sum=0;
    for(int i=0; i<n; ++i) {
        for(auto &to:adj[i]) {
            sum+=w[to]+max_path[to];
        }
    }
    int q;
    cin >> q;
    cout << sum << endl;
    for(int g=0; g<q; ++g) {
        sum=0;
        int n, increment;
        cin >> n >> increment;
        update(n, increment, p, w, max_path);
        for(int i=0; i<n; ++i) {
            for(auto &to:adj[i]) {
                sum+=w[to]+max_path[to];
            }
        }
        cout << sum << endl;
    }
    /*for(auto &elem:max_path) cout << elem << " ";
    cout << endl;
    for(auto &elem:max_path) cout << elem << " ";*/
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

arboras.cpp: In function 'long long int update(long long int, long long int, long long int*, long long int*, std::vector<long long int>&)':
arboras.cpp:29:1: warning: no return statement in function returning non-void [-Wreturn-type]
   29 | }
      | ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 31
• Subtask 4: 0 / 45