Submission #1370860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370860		edga1	Tree (IOI24_tree)	C++20	10 / 100	2095 ms	22792 KiB

tree

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
#include "tree.h"
using namespace std;

const int N=200005;
vector<int> g[N];
int w[N];
int n,l,r;
ll atb;

ll dfs(int v, int p){
    if(g[v].size()==1 && v!=0){
        atb+=(ll)w[v]*l;
        return l;
    }
    ll sum=0;
    for(auto u : g[v]){
        if(u==p) continue;
        sum+=dfs(u,v);
    }
    if(sum<=r) return sum;
    atb+=(sum-r)*w[v];
    return r;
}

void init(vector<int> P, vector<int> W) {
    n=(int)P.size();
    for(int i=0; i<n; i++) w[i]=W[i];
    for(int i=1; i<n; i++){
        g[i].pb(P[i]);
        g[P[i]].pb(i);
    }
}

long long query(int L, int R) {
    l=L; r=R;
    atb=0;
    dfs(0,0);
    return atb;
}

• 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