oj.uz

Submission #753394

# Submission time Handle Problem Language Result Execution time Memory
753394 2023-06-05T06:57:17 Z keta_tsimakuridze Arboras (RMI20_arboras) C++14
24 / 100
 5000 ms 15016 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);
    cout << ans << endl;
    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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5076 KB Output is correct
2 Correct 9 ms 5076 KB Output is correct
3 Correct 5 ms 5016 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 13160 KB Output is correct
2 Correct 257 ms 10936 KB Output is correct
3 Correct 248 ms 11680 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5076 KB Output is correct
2 Correct 9 ms 5076 KB Output is correct
3 Correct 5 ms 5016 KB Output is correct
4 Correct 280 ms 13160 KB Output is correct
5 Correct 257 ms 10936 KB Output is correct
6 Correct 248 ms 11680 KB Output is correct
7 Execution timed out 5027 ms 15016 KB Time limit exceeded
8 Halted 0 ms 0 KB -