Submission #1282006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282006		ducdev	Grapevine (NOI22_grapevine)	C++17	0 / 100	787 ms	134392 KiB

Main

// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef pair<int, int> ii;

const int MAX_N = 1e5;
const int MOD = 1e9 + 7;
const ll INF = 1e18;

struct SegmentTree {
    vector<ll> seg, lazy;
    int n;

    void down(int node) {
        for (int i = 0; i < 2; i++) {
            seg[node << 1 | i] += lazy[node];
            lazy[node << 1 | i] += lazy[node];
        };
        lazy[node] = 0;
    };

    void assign(int pos, ll val) {
        int l = 1, r = n, node = 1;

        while (l < r) {
            int mid = (l + r) >> 1;
            if (lazy[node]) down(node);

            if (pos <= mid) {
                node <<= 1;
                r = mid;
            } else {
                (node <<= 1) |= 1;
                l = mid + 1;
            };
        };

        seg[node] = val;
        while (node > 1) {
            node >>= 1;
            seg[node] = min(seg[node << 1], seg[node << 1 | 1]);
        };
    };

    void update(int node, int l, int r, int u, int v, int val) {
        if (l > v || r < u) return;

        if (l >= u && r <= v) {
            seg[node] += val;
            lazy[node] += val;
            return;
        };

        int mid = (l + r) >> 1;
        if (lazy[node]) down(node);

        update(node << 1, l, mid, u, v, val);
        update(node << 1 | 1, mid + 1, r, u, v, val);

        seg[node] = min(seg[node << 1], seg[node << 1 | 1]);
    };

    void update(int l, int r, int val) {
        update(1, 1, n, l, r, val);
    };

    ll getMin() {
        return seg[1];
    };

    SegmentTree() {};
    SegmentTree(int n) : n(n) {
        seg.assign(4 * n + 5, INF);
        lazy.assign(4 * n + 5, 0);
    };
};

struct FenwickTree {
    int n;
    vector<ll> bit;

    void update(int pos, int val) {
        for (; pos <= n; pos += pos & (-pos))
            bit[pos] += val;
    };

    ll get(int pos) {
        ll ret = 0;
        for (; pos > 0; pos -= pos & (-pos))
            ret += bit[pos];
        return ret;
    };

    FenwickTree() {};
    FenwickTree(int n) : n(n) {
        bit.assign(n + 5, 0);
    };
};

int n, q, timer, lg;
int par[MAX_N + 5], sz[MAX_N + 5], tin[MAX_N + 5], tout[MAX_N + 5], edgeWeight[MAX_N + 5];
int up[MAX_N + 5][18];
bool del[MAX_N + 5], grap[MAX_N + 5];
ll f[MAX_N + 5];
vector<int> centNode[MAX_N + 5];
vector<ii> adj[MAX_N + 5];
SegmentTree seg[MAX_N + 5];
FenwickTree bit;

void preDfs(int u, int p) {
    tin[u] = ++timer;
    up[u][0] = p;

    for (int i = 1; i <= lg; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];

    for (ii e : adj[u]) {
        int v = e.first, w = e.second;
        if (v == p) continue;
        edgeWeight[v] = w;
        f[v] = f[u] + w;
        preDfs(v, u);
    };

    tout[u] = timer;
};

bool isAncestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
};

int __lca(int u, int v) {
    if (isAncestor(u, v)) return u;
    if (isAncestor(v, u)) return v;

    for (int i = lg; i >= 0; i--)
        if (!isAncestor(up[u][i], v))
            u = up[u][i];

    return up[u][0];
};

ll dist(int u, int v) {
    return f[u] + f[v] - f[__lca(u, v)] * 2;
};

void calcSize(int u, int p) {
    sz[u] = 1;
    for (ii e : adj[u]) {
        int v = e.first;
        if (v == p || del[v]) continue;
        calcSize(v, u);
        sz[u] += sz[v];
    };
};

int findCentroid(int u, int p, int n) {
    for (ii e : adj[u]) {
        int v = e.first;
        if (v == p || del[v]) continue;
        if (sz[v] * 2 > n) return findCentroid(v, u, n);
    };
    return u;
};

void collectNode(int root, int u, int p) {
    centNode[root].push_back(u);
    for (ii e : adj[u]) {
        int v = e.first;
        if (v == p || del[v]) continue;
        collectNode(root, v, u);
    };
};

void decompose(int u, int p) {
    calcSize(u, u);

    int centroid = findCentroid(u, u, sz[u]);
    par[centroid] = p;
    del[centroid] = true;

    collectNode(centroid, centroid, centroid);

    sort(all(centNode[centroid]), [&](int u, int v) {
        return tin[u] < tin[v];
    });

    for (ii e : adj[centroid]) {
        int v = e.first;
        if (del[v]) continue;
        decompose(v, centroid);
    };
};

ll sumPath(int u, int v) {
    return bit.get(tin[u]) + bit.get(tin[v]) - bit.get(tin[__lca(u, v)]) * 2;
};

ll query(int u) {
    ll res = INF;

    for (int v = u; v != 0; v = par[v]) {
        res = min(res, sumPath(u, v) + seg[v].getMin());
    };

    return res;
};

int findLeft(int x, const vector<int>& data) {
    int l = 0, r = (int)data.size() - 1, pos = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (tin[data[mid]] >= x) {
            pos = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    };
    return pos;
};

int findRight(int x, const vector<int>& data) {
    int l = 0, r = (int)data.size() - 1, pos = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (tin[data[mid]] <= x) {
            pos = mid;
            l = mid + 1;
        } else
            r = mid - 1;
    };
    return pos;
};

void updateGrap(int u) {
    grap[u] ^= 1;

    for (int v = u; v != 0; v = par[v]) {
        int idx = findLeft(tin[u], centNode[v]) + 1;
        ll val = grap[u] ? sumPath(u, v) : INF;
        seg[v].assign(idx, val);
    };
};

void updateWeight(int u, int delta) {
    for (int v = par[u]; v != 0; v = par[v]) {
        int l = findLeft(tin[u], centNode[v]) + 1;
        if (l == 0) continue;
        int r = findRight(tout[u], centNode[v]) + 1;
        seg[v].update(l, r, delta);
    };
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("MAIN.INP", "r")) {
        freopen("MAIN.INP", "r", stdin);
        freopen("MAIN.OUT", "w", stdout);
    };

    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(ii(v, w));
        adj[v].push_back(ii(u, w));
    };

    lg = ceil(log2(n));
    preDfs(1, 1);
    decompose(1, 0);

    int cntGrap = 0;

    for (int u = 1; u <= n; u++) {
        seg[u] = SegmentTree(centNode[u].size());
    };

    bit = FenwickTree(n);
    for (int u = 2; u <= n; u++) {
        bit.update(tin[u], edgeWeight[u]);
        bit.update(tout[u] + 1, -edgeWeight[u]);
    };

    while (q--) {
        int type, u;
        cin >> type >> u;
        if (type == 1) {
            cout << (cntGrap == 0 ? -1 : query(u)) << '\n';
        };

        if (type == 2) {
            cntGrap += (grap[u] ? -1 : 1);
            updateGrap(u);
        };

        if (type == 3) {
            int v, newWeight;
            cin >> v >> newWeight;
            if (isAncestor(v, u)) swap(u, v);

            int delta = -edgeWeight[v] + newWeight;

            bit.update(tin[v], delta);
            bit.update(tout[v] + 1, -delta);

            updateWeight(v, delta);

            edgeWeight[v] = newWeight;
        };
    };
};

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:262:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  262 |         freopen("MAIN.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:263:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  263 |         freopen("MAIN.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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