Submission #1200863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200863		onbert	Tree (IOI24_tree)	C++20	18 / 100	66 ms	20384 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, INF = 1e9;
int n;
vector<int> adj[maxn];
int fa[maxn], w[maxn];

int leaf = 0;
int sz;
vector<pair<int,int>> vec = {{0, 0}};
int dfs(int u) {
    if (w[u] && !adj[u].size()) leaf++;
    if (w[u] == 0 || !adj[u].size()) return 1;
    int cnt = 0;
    for (int v:adj[u]) cnt += dfs(v);
    return cnt;
}

void init(vector<int32_t> P, vector<int32_t> W) {
    n = P.size();
    for (int i=1;i<n;i++) adj[P[i]].push_back(i), fa[i] = P[i];
    for (int i=0;i<n;i++) w[i] = W[i];
    for (int i=0;i<n;i++) if ((i == 0 || w[fa[i]] == 0) && w[i]) {
        int val = dfs(i);
        vec.push_back({val, val});
    }
    vec.push_back({INF, 0});
    sort(vec.begin(), vec.end());
    sz = vec.size();
    for (int i=1;i<sz;i++) vec[i].second += vec[i-1].second;
    // for (auto [x, y]:vec) cout << x << " " << y << endl;
}

long long query(int32_t L, int32_t R) {
    int l = 0, r = sz-1;
    while (l < r) {
        int mid = (l+r)/2;
        if (L * vec[mid].first - R >= 0) r = mid;
        else l = mid+1;
    }
    return L * (vec[sz-1].second - vec[l-1].second) - R * ((sz-2) - l + 1) + leaf * L;
}

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