Submission #1125657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125657		ShadowShark	Grapevine (NOI22_grapevine)	C++20	100 / 100	1126 ms	198400 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 5;
const long long inf = 1e18;
int n, q;

/// Segment Treee
struct node {
    long long dis, val, lazy;
};

vector<node> st[maxN];
int statusGrape[maxN]; long long ngaos[maxN];

void down(int type, int id) {
    long long t = st[type][id].lazy;
    if (!t) return ;

    st[type][2 * id].lazy += t;
    st[type][2 * id].dis += t;
    st[type][2 * id].val += t;

    st[type][2 * id + 1].lazy += t;
    st[type][2 * id + 1].dis += t;
    st[type][2 * id + 1].val += t;

    st[type][id].lazy = 0;
}

void build(int type, int id, int l, int r) {
    if (l == r) {
        st[type][id].dis = ngaos[l];
        st[type][id].val = inf;
        st[type][id].lazy = 0;
        return ;
    }

    int mid = (l + r) >> 1;

    build(type, 2 * id, l, mid);
    build(type, 2 * id + 1, mid + 1, r);

    st[type][id].val = min(st[type][2 * id].val, st[type][2 * id + 1].val);
}

void updateRange(int type, int id, int l, int r, int u, int v, long long val) {
    if (v < l || r < u) return ;

    if (u <= l && r <= v) {
        st[type][id].lazy += val;
        st[type][id].dis += val;
        st[type][id].val += val;
        return ;
    }

    int mid = (l + r) >> 1;
    down(type, id);

    updateRange(type, 2 * id, l, mid, u, v, val);
    updateRange(type, 2 * id + 1, mid + 1, r, u, v, val);

    st[type][id].val = min(st[type][2 * id].val, st[type][2 * id + 1].val);
}

void updateState(int type, int id, int l, int r, int pos, int grapeState) {
    if (l == r) {
        if (grapeState) st[type][id].val = st[type][id].dis;
            else st[type][id].val = inf;
        return ;
    }

    int mid = (l + r) >> 1;
    down(type, id);

    if (pos <= mid) updateState(type, 2 * id, l, mid, pos, grapeState);
        else updateState(type, 2 * id + 1, mid + 1, r, pos, grapeState);

    st[type][id].val = min(st[type][2 * id].val, st[type][2 * id + 1].val);
}

long long getDis(int type, int id, int l, int r, int pos) {
    if (l == r) return st[type][id].dis;

    int mid = (l + r) >> 1;
    down(type, id);

    if (pos <= mid) return getDis(type, 2 * id, l, mid, pos);
    return getDis(type, 2 * id + 1, mid + 1, r, pos);
}

/// Build Centroid
vector<int> adj[maxN];
map<pair<int, int>, int> weight;
int sz[maxN], par_cen[maxN];

void dfs_sz(int u, int pre) {
    sz[u] = 1;
    for (auto v: adj[u]) {
        if (v == pre || par_cen[v]) continue;
        dfs_sz(v, u);
        sz[u] += sz[v];
    }
}

int getCentroid(int u, int pre, int m) {
    for (auto v: adj[u]) {
        if (v == pre || par_cen[v]) continue;
        if (sz[v] > m / 2) return getCentroid(v, u, m);
    }
    return u;
}

int timeDfs = 0;
int layer[maxN], in[21][maxN], out[21][maxN], st_size[maxN];
long long depth[maxN];

void preDfs(int centroid, int u, int pre) {
    in[layer[centroid]][u] = ++timeDfs;
    ngaos[timeDfs] = depth[u];

    for (auto v: adj[u]) {
        if (v == pre || par_cen[v]) continue;
        depth[v] = depth[u] + weight[{u, v}];

        preDfs(centroid, v, u);
    }
    out[layer[centroid]][u] = timeDfs;
}

void build_centroid(int u, int pre) {
    dfs_sz(u, pre); int m = sz[u];
    int centroid = getCentroid(u, pre, m);

    par_cen[centroid] = pre;
    st[centroid].resize(4 * m + 6);
    st_size[centroid] = m;
    layer[centroid] = (pre == -1 ? 1 : layer[par_cen[centroid]] + 1);

    timeDfs = 0;
    depth[centroid] = 0;
    preDfs(centroid, centroid, pre);
    build(centroid, 1, 1, st_size[centroid]);

    for (auto v: adj[centroid]) {
        if (par_cen[v]) continue;
        build_centroid(v, centroid);
    }
}

void debug_dis() {
    cout << "Debug_dis\n";
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= st_size[i]; j++)
            cout << getDis(i, 1, 1, st_size[i], j) << ' ';
        cout << '\n';
    }
    cout << '\n';
}

int similar(int u, int v) {
    if (layer[u] < layer[v]) swap(u, v);

    while (layer[u] > layer[v]) u = par_cen[u];

    while (u != v) {
        u = par_cen[u];
        v = par_cen[v];
    }

    return u;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("grapevine.inp", "r", stdin);
    //freopen("grapevine.ans", "w", stdout);

    cin >> n >> q;

    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        adj[u].push_back(v);
        adj[v].push_back(u);

        weight[{u, v}] = weight[{v, u}] = w;
    }

    build_centroid(1, -1);

    while (q--) {
        int type, u;
        cin >> type >> u;

        if (type == 1) {
            long long res = inf; int x = u;

            while (x != -1) {
                res = min(res, st[x][1].val + getDis(x, 1, 1, st_size[x], in[layer[x]][u]));
                x = par_cen[x];
            }

            if (res > 1e14) cout << -1 << '\n';
                else cout << res << '\n';
        }
        else if (type == 2) {
            statusGrape[u] ^= 1;
            int x = u;
            while (x != -1) {
                updateState(x, 1, 1, st_size[x], in[layer[x]][u], statusGrape[u]);
                x = par_cen[x];
            }
        }
        else {
            int v, w;
            cin >> v >> w;
            int prev_weight = weight[{u, v}];
            int x = similar(u, v);

            while (x != -1) {
                int l, r;
                if (in[layer[x]][u] < in[layer[x]][v]) {
                    l = in[layer[x]][v];
                    r = out[layer[x]][v];
                }
                else {
                    l = in[layer[x]][u];
                    r = out[layer[x]][u];
                }

                updateRange(x, 1, 1, st_size[x], l, r, w - prev_weight);
                x = par_cen[x];
            }

            weight[{u, v}] = weight[{v, u}] = w;
        }
    }

    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 18 / 18
• Subtask 6: 32 / 32