제출 #753393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
753393		keta_tsimakuridze	Arboras (RMI20_arboras)	C++14	0 / 100	5042 ms	16952 KiB

arboras

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, ans, id[N], p[N];
pii mx[N][2];
vector<pii> V[N];
void dfs(int u) {
    for(int i = 0; i < V[u].size(); i++) {
        int v = V[u][i].f, d = V[u][i].s;
        dfs(v);
        if(mx[v][0].f + d > mx[u][0].f) swap(mx[u][0], mx[u][1]), mx[u][0] = {mx[v][0].f + d, v};
        else mx[u][1] = max(mx[u][1], {mx[v][0].f + d, v});
    }
    ans += mx[u][0].f + mx[u][1].f; ans %= mod;
}

void up(int v) {
    if(!v) return;
    int u = p[v];
    ans -= mx[u][0].f + mx[u][1].f;
    ans = (ans + 2 * mod) % mod;
    if(mx[u][0].f <= mx[v][0].f + V[u][id[v]].s) {
        if(mx[u][0].s == v) mx[u][0].f = mx[v][0].f + V[u][id[v]].s;
        else swap(mx[u][0], mx[u][1]), mx[u][0] = {mx[v][0].f + V[u][id[v]].s, v};
    } else mx[u][1] = max(mx[u][1],  {mx[v][0].f + V[u][id[v]].s, v});
    ans += mx[u][0].f + mx[u][1].f;
    ans %= mod;
    up(u);
}
main(){
    int n;
    cin >> n;
    for(int i = 1; i < n; i++) cin >> p[i];
    for(int i = 1; i < n; i++) {
        int d;
        cin >> d;
        id[i] = (int)V[p[i]].size();
        V[p[i]].push_back({i, d});
    }
    dfs(0);
    int q;
    cin >> q;
    while(q--) {
        int u, d;
        cin >> u >> d;

        V[p[u]][id[u]].s += d;
        up(u);
        cout << ans << "\n";
    }
 }

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

arboras.cpp: In function 'void dfs(long long int)':
arboras.cpp:12:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
arboras.cpp: At global scope:
arboras.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main(){
      | ^~~~

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