Submission #1129631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129631		c0det1ger	Tree (IOI24_tree)	C++20	17 / 100	2095 ms	19556 KiB

tree

#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define double long double

vector<int> e[200005];
vector<int> w;
long long sum = 0;
int tc = 0;
long long ma = 0;

void dfs2(int x){
    int cnt = 0;
    for (int y: e[x]){
        cnt++;
        dfs2(y);
    }
    if (cnt == 0){
        sum++;
    }
    else{
        sum += (cnt - 1);
        ma += (cnt - 1);
    }
}

void init(vector<int> P, vector<int> W){
    w = W;
    
    ma = 0;
    tc = 0;
    int mi = 1e9, ma = 0;
    for (int x: W){
        mi = min(mi, x);
        ma = max(ma, x);
    }
    for (int i = 1; i < P.size(); i++){
        e[P[i]].push_back(i);
    }
    if (mi == ma && mi ==1){
        tc = 4;
    }
    if (tc == 4){
        sum = 0;
        dfs2(0);
    }
}

long long ans = 0;
long long l, r;

long long dfs(int x){
    long long a = 0;
    for (int y: e[x]){
        a += dfs(y);
    }
    if (a == 0){
        ans += (long long)w[x] * l;
        return l;
    }
    else if (a > r){
        ans += (long long)w[x] * (a - r);
        return r;
    }
    return a;
}

long long query(int L, int R){
    if (tc == 4){
        return sum * L - (min((long long)R - L, ma * L));
    }
    l = L;
    r = R;
    ans = 0;
    dfs(0);
    return ans;
}

/*
 ____   ___    ___     ____  _____          ____    ____   ___
|      |   |  |   \   |        |     /|    |       |      |   \
|      |   |  |    |  |____    |      |    |   _   |____  |___/
|      |   |  |    |  |        |      |    |    |  |      |  \
|____  |___|  |___/   |____    |    __|__  |____|  |____  |   \
 
*/

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 7 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19