Submission #1210666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210666		trimkus	Tree (IOI24_tree)	C++20	Compilation error	0 ms	0 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static const int MAXN = 60000;

int N;
vector<int> W;
vector<vector<int>> adj;
vector<int> P;

int sz[MAXN], heavy[MAXN], depth[MAXN];
int head[MAXN], pos[MAXN], cur_pos;
vector<int> base;

int tin[MAXN], tout[MAXN];
int timerDFS;

struct SegTree {
    int n;
    vector<ll> st, lazy;

    SegTree(int _n = 0) {
        init(_n);
    }

    void init(int _n) {
        n = _n;
        st.assign(4 * n, 0LL);
        lazy.assign(4 * n, 0LL);
    }

    void push(int idx, int L, int R) {
        if (lazy[idx] != 0 && L < R) {
            ll val = lazy[idx];
            int mid = (L + R) >> 1;
            st[idx<<1]   += val;
            lazy[idx<<1] += val;
            st[idx<<1|1]   += val;
            lazy[idx<<1|1] += val;
            lazy[idx] = 0;
        } else if (L == R) {
            lazy[idx] = 0;
        }
    }

    void update_range(int idx, int L, int R, int i, int j, ll val) {
        if (i > R || j < L) return;
        if (i <= L && R <= j) {
            st[idx]   += val;
            lazy[idx] += val;
            return;
        }
        push(idx, L, R);
        int mid = (L + R) >> 1;
        update_range(idx<<1,   L,    mid, i, j, val);
        update_range(idx<<1|1, mid+1, R,   i, j, val);
        st[idx] = min(st[idx<<1], st[idx<<1|1]);
    }

    ll query_min(int idx, int L, int R, int i, int j) {
        if (i > R || j < L) return LLONG_MAX;
        if (i <= L && R <= j) {
            return st[idx];
        }
        push(idx, L, R);
        int mid = (L + R) >> 1;
        return min(
            query_min(idx<<1,   L,    mid, i, j),
            query_min(idx<<1|1, mid+1, R,   i, j)
        );
    }

    void update_range(int l, int r, ll val) {
        if (l > r) return;
        update_range(1, 0, n-1, l, r, val);
    }
    ll query_min(int l, int r) {
        if (l > r) return LLONG_MAX;
        return query_min(1, 0, n-1, l, r);
    }
};

SegTree seg;


int dfs_size(int v) {
    sz[v] = 1;
    heavy[v] = -1;
    int maxSize = 0;
    for (int u : adj[v]) {
        if (u == P[v]) continue;
        depth[u] = depth[v] + 1;
        int childSize = dfs_size(u);
        if (childSize > maxSize) {
            maxSize = childSize;
            heavy[v] = u;
        }
        sz[v] += childSize;
    }
    return sz[v];
}

// 2) Second DFS: assign head[] and pos[], fill up base[]
void decompose(int v, int h) {
    head[v] = h;
    pos[v]  = cur_pos;
    base[cur_pos++] = 0;  // we store 0 as the initial sum at each node

    if (heavy[v] != -1) {
        // Continue the same chain
        decompose(heavy[v], h);
    }
    // Any child that is not heavy starts a new chain
    for (int u : adj[v]) {
        if (u == P[v] || u == heavy[v]) continue;
        decompose(u, u);
    }
}
int cnt;
void init(vector<int> _P, vector<int> _W) {
    P = _P;
    P[0] = -1;

    W = _W;
    N = (int)P.size();

    adj.assign(N, {});
    for (int i = 1; i < N; i++) {
        adj[P[i]].push_back(i);
        adj[i].push_back(P[i]);
    }
    for (int i = 1; i < N; ++i) {
      if ((int)leaves[i].size() == 1) {
        cnt++;
      }
    }
}


// Add +delta to all nodes on the path from v up to root (0).
void path_update(int v, ll delta) {
    while (head[v] != head[0]) {
        seg.update_range(pos[ head[v] ], pos[v], delta);
        v = P[ head[v] ];
    }
    seg.update_range(pos[0], pos[v], delta);
}

// Query the minimum value among all ancestors of v (including v).
ll path_query_min(int v) {
    ll res = LLONG_MAX;
    while (head[v] != head[0]) {
        res = min(res, seg.query_min(pos[ head[v] ], pos[v]));
        v = P[ head[v] ];
    }
    res = min(res, seg.query_min(pos[0], pos[v]));
    return res;
}

ll get_sum(int v) {
    return seg.query_min(pos[v], pos[v]);
}
priority_queue<pair<int, int>> leaves[MAXN];
vector<int> ptr(MAXN);
// bool inq[MAXN];
int degree[MAXN];

long long query(int L, int R) {
    cerr << "Query " << L << " " << R << "\n";

    ll res = 1LL * cnt * L + max(0LL, 1LL * cnt * L - R);
    return res;
}

Compilation message (stderr)

tree.cpp: In function 'void init(std::vector<int>, std::vector<int>)':
tree.cpp:135:16: error: 'leaves' was not declared in this scope
  135 |       if ((int)leaves[i].size() == 1) {
      |                ^~~~~~