Submission #1286941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286941		MMihalev	Tree (IOI24_tree)	C++20	10 / 100	2096 ms	20480 KiB

tree

#include<iostream>
#include<algorithm>
#include<vector>
#include "tree.h"
using namespace std;
const int MAX_N=2e5+5;
long long w[MAX_N];
vector<int>g[MAX_N];
int deg[MAX_N];
long long sumcoef[MAX_N];
int n;
long long l,r;
long long ans;

void dfs(int u)
{
    for(int v:g[u])
    {
        dfs(v);
        sumcoef[u]+=sumcoef[v];
    }
    if(deg[u]==0)
    {
        sumcoef[u]=l;
        ans+=l*w[u];
    }
    else
    {
        if(sumcoef[u]>r)
        {
            long long dif=sumcoef[u]-r;
            ans+=dif*w[u];
            sumcoef[u]=r;
        }
    }
}
void init(std::vector<int> P, std::vector<int> W)
{
    n=P.size();
    w[0]=W[0];
    for(int i=1;i<n;i++)
    {
        w[i]=W[i];
        deg[P[i]]++;
        g[P[i]].push_back(i);
    }
}

long long query(int L, int R)
{
    l=L;
    r=R;
    ans=0;
    for(int i=0;i<n;i++)sumcoef[i]=0;
    dfs(0);
    return ans;
}

• 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