Submission #1125649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125649		tuannm	Grapevine (NOI22_grapevine)	C++20	0 / 100	851 ms	84156 KiB

Main

#include<bits/stdc++.h>
#define ii pair<int, int>
#define ll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod[2] = {1000000007, 998244353};
const int N = 1e5 + 1;
const string NAME = "";
int n, q;
vector<ii> adj[N];

int lg[2 * N], euler[19][2 * N], tin[N], tout[N], EulerTourTraversal;

void DFS_EulerTour(int u = 1, int p = 0){
    tin[u] = ++EulerTourTraversal;
    euler[0][EulerTourTraversal] = u;

    for(auto [v, w] : adj[u]){
        if(v == p)
            continue;

        DFS_EulerTour(v, u);
        euler[0][++EulerTourTraversal] = u;
    }

    tout[u] = EulerTourTraversal;
}

int min_by_time(int u, int v){
    return tin[u] < tin[v] ? u : v;
}

int LCA(int u, int v){
    int l = min(tin[u], tin[v]), r = max(tout[u], tout[v]);
    int k = lg[r - l + 1];

    return min_by_time(euler[k][l], euler[k][r - (1 << k) + 1]);
}

void initEulerTour(){
    DFS_EulerTour();

    for(int i = 2; i <= EulerTourTraversal; ++i)
        lg[i] = lg[i / 2] + 1;

    for(int l = 1; l <= lg[EulerTourTraversal]; ++l)
        for(int i = 1; i <= EulerTourTraversal - (1 << l) + 1; ++i)
            euler[l][i] = min_by_time(euler[l - 1][i], euler[l - 1][i + (1 << (l - 1))]);
}

const long long inf = 1e16;

struct SegmentTree{
    int n, h;
    vector<long long> tree, lazy;

    SegmentTree(int _n = 0) : n(_n){
        tree.resize(2 * n, 0);
        lazy.resize(n, 0);
        h = sizeof(int) * 8 - __builtin_clz(n);
    }

    void up(int u){
        while(u > 1)
            u >>= 1, tree[u] = min(tree[u << 1], tree[u << 1 | 1]) + lazy[u];
    }

    void apply(int u, long long val){
        tree[u] += val;
        if(u < n)
            lazy[u] += val;
    }

    void down(int u){
        for(int s = h; s; --s){
            int i = u >> s;

            if(lazy[i]){
                apply(i << 1, lazy[i]);
                apply(i << 1 | 1, lazy[i]);
                lazy[i] = 0;
            }
        }
    }

    void update(int l, int r, long long val){
        --l;
        l += n, r += n;
        int l0 = l, r0 = r;

        for(; l < r; l >>= 1, r >>= 1){
            if(l & 1)
                apply(l++, val);

            if(r & 1)
                apply(--r, val);
        }

        up(l0);
        up(r0 - 1);
    }

    long long get(int l, int r){
        --l;
        l += n, r += n;
        down(l);
        down(r - 1);

        long long res = 2LL * inf;

        for(; l < r; l >>= 1, r >>= 1){
            if(l & 1)
                res = min(res, tree[l++]);

            if(r & 1)
                res = min(tree[--r], res);
        }

        return res;
    }
};

SegmentTree d;
int L[N], R[N], unused_variables_number_1;
long long W[N];

void DFS_TraversalOrder(int u = 1, int p = 0){
    L[u] = ++unused_variables_number_1;

    for(auto [v, w] : adj[u]){
        if(v == p)
            continue;

        W[v] = w;
        DFS_TraversalOrder(v, u);
    }

    R[u] = unused_variables_number_1;
}

long long dist(int u, int v){
    int lca_uv = LCA(u, v);
    return d.get(L[u], L[u]) + d.get(L[v], L[v]) - 2LL * d.get(L[lca_uv], L[lca_uv]);
}

int CurrentGrapes;
bool GrapeTree[N];

SegmentTree Node[N];
int sz[N];
bool del[N];
vector<int> g[N];
stack<int> stk;
int CentroidRoot;
int CenPar[N], depthCentroid[N];

void DFS_centroid(int u, int p = 0){
    sz[u] = 1;

    for(auto [v, w] : adj[u]){
        if(v == p || del[v])
            continue;

        DFS_centroid(v, u);
        sz[u] += sz[v];
    }
}

int centroid(int u, int p, int n){
    for(auto [v, w] : adj[u]){
        if(v == p || del[v])
            continue;

        if(sz[v] > n / 2)
            return centroid(v, u, n);
    }

    return u;
}

void decom(int u = 1){
    DFS_centroid(u);
    int root = centroid(u, 0, sz[u]);

    if(stk.empty())
        CentroidRoot = root;

    if(!stk.empty())
        g[stk.top()].pb(root), CenPar[root] = stk.top();

    stk.push(root);
    del[root] = true;

    for(auto [v, w] : adj[root])
        if(!del[v])
            decom(v);

    stk.pop();
}

void createChildID(int u){
    int m = g[u].size();
    for(int i = 0; i < m; ++i){
        int v = g[u][i];
        depthCentroid[v] = depthCentroid[u] + 1;
        createChildID(v);
        for(int zz : g[v])
            g[u].pb(zz);
    }

    g[u].pb(u);
    sort(g[u].begin(), g[u].end());
    g[u].resize(unique(g[u].begin(), g[u].end()) - g[u].begin());
    m = g[u].size();
    Node[u] = SegmentTree(m);
    for(int i = 0; i < m; ++i)
        Node[u].update(i + 1, i + 1, dist(u, g[u][i]) + inf);
}

void inp(){
    cin >> n >> q;

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

        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
}

void solve(){
    d = SegmentTree(n);
    initEulerTour();
    DFS_TraversalOrder();

    for(int i = 1; i <= n; ++i)
        d.update(L[i], R[i], W[i]);

    decom();
    createChildID(CentroidRoot);

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

        if(type == 1){
            int u;
            cin >> u;

            if(!CurrentGrapes){
                cout << "-1\n";
                continue;
            }

            int v = u;
            long long ans = inf;
            while(v != 0){
                ans = min(ans, Node[v].get(1, g[v].size()) + dist(u, v));
                v = CenPar[v];
            }

            cout << ans << "\n";
        }
        else if(type == 2){
            int u;
            cin >> u;

            if(GrapeTree[u]){
                --CurrentGrapes;
                GrapeTree[u] = false;
                int v = u;

                while(v != 0){
                    int idx = lower_bound(g[v].begin(), g[v].end(), u) - g[v].begin() + 1;
                    Node[v].update(idx, idx, inf);
                    v = CenPar[v];
                }
            }
            else{
                ++CurrentGrapes;
                GrapeTree[u] = true;
                int v = u;

                while(v != 0){
                    int idx = lower_bound(g[v].begin(), g[v].end(), u) - g[v].begin() + 1;
                    Node[v].update(idx, idx, -inf);
                    v = CenPar[v];
                }
            }
        }
        else{
            int u, v, w;
            cin >> u >> v >> w;
            int z = u + v - LCA(u, v);

            if(depthCentroid[u] > depthCentroid[v])
                swap(u, v);
            int vv = v;

            while(vv != CenPar[u]){
                int idx = lower_bound(g[vv].begin(), g[vv].end(), v) - g[vv].begin() + 1;
                Node[vv].update(idx, idx, -dist(v, vv));
                vv = CenPar[vv];
            }

            d.update(L[z], R[z], -W[z]);
            W[z] = w;
            d.update(L[z], R[z], W[z]);

            vv = v;

            while(vv != CenPar[u]){
                int idx = lower_bound(g[vv].begin(), g[vv].end(), v) - g[vv].begin() + 1;
                Node[vv].update(idx, idx, dist(vv, v));
                vv = CenPar[vv];
            }
        }
    }
}

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

    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }

    inp();
    solve();
}

/*
7 11
1 2 2
2 3 4
5 6 1
5 3 6
3 7 6
2 4 9
2 6
2 4
2 7
1 1
3 2 3 0
1 1
3 6 5 0
1 1
3 3 5 0 3 2 4 0
1 1
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:330:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  330 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:331:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  331 |         freopen((NAME + ".out").c_str(), "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