oj.uz

Submission #753393

# Submission time Handle Problem Language Result Execution time Memory
753393 2023-06-05T06:56:26 Z keta_tsimakuridze Arboras (RMI20_arboras) C++14
0 / 100
 5000 ms 16952 KB 
#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";
    }
 }

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 287 ms 15264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5042 ms 16952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -