Submission #1125643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125643		SoMotThanhXuan	Grapevine (NOI22_grapevine)	C++20	14 / 100	1112 ms	236808 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define mp make_pair
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
inline bool maximize(int &u, int v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
inline bool minimize(int &u, int v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
inline bool maximizell(long long &u, long long v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
inline bool minimizell(long long &u, long long v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
const int mod = 1e9 + 7;
inline int fastPow(int a, int n){
    int res = 1;
    while(n){
        if(n & 1)res = 1ll * res * a * mod;
        a = 1ll * a * a % mod;
        n >>= 1;
    }
    return res;
}
inline void add(int &u, int v){
    u += v;
    if(u >= mod) u -= mod;
}
inline void sub(int &u, int v){
    u -= v;
    if(u < 0) u += mod;
}
const int maxN = 1e5 + 5;
const int inf = 2e9;
const long long infll = 1e18;
const long long lim = 1e14 + 222;
int par[maxN], sz[maxN], numNode, n, q;
vector<pair<int, int>> adj[maxN];
int depth[maxN], p[maxN], val[maxN], lg[maxN << 1], min_depth[18][maxN << 1], tour[maxN << 1], cnt, in[maxN], out[maxN], timeDfs;
long long d[maxN];
void dfsLca(int u = 1, int pre = 0){
    tour[++cnt] = u;
    p[u] = cnt;
    in[u] = ++timeDfs;
    for(auto[v, w] : adj[u]){
        if(v != pre){
            val[v] = w;
            depth[v] = depth[u] + 1;
            d[v] = d[u] + w;
            dfsLca(v, u);
            tour[++cnt] = u;
        }
    }
    out[u] = timeDfs;
}
int getMin(int u, int v){
    return depth[u] < depth[v] ? u : v;
}
int lca(int u, int v){
    int l = p[u], r = p[v];
    if(l > r)swap(l, r);
    int k = lg[r - l + 1];
    return getMin(min_depth[k][l], min_depth[k][r - (1 << k) + 1]);
}
void reSize(int u, int p){
    sz[u] = 1;
    for(auto[v, w] : adj[u]){
        if(v != p && par[v] == 0){
            reSize(v, u);
            sz[u] += sz[v];
        }
    }
}
int getCentroid(int u, int p){
    for(auto[v, w] : adj[u]){
        if(v != p && par[v] == 0){
            if((sz[v] << 1) > numNode) return getCentroid(v, u);
        }
    }
    return u;
}
void build(int u = 1, int p = n + 1){
    reSize(u, p);
    numNode = sz[u];
    int c = getCentroid(u, p);
    par[c] = p;
    for(auto[v, w] : adj[c]){
        if(v != p && par[v] == 0){
            build(v, c);
        }
    }
}
struct Node{
    long long d, answer;
    bool state;
    Node(){
        d = answer = infll;
        state = false;
    }
    Node operator + (const Node &rhs) const {
        if(answer < rhs.answer) return *this;
        return rhs;
    }
};
struct Interval{
    int root, numNode;
    vector<int> node;
    vector<Node> it;
    vector<long long> lz;
    void reSize(int n = 0){
        it.resize(n << 2, Node());
        lz.resize(n << 2, 0);
        numNode = n;
    }
    void init(int id, int l, int r){
        if(l == r){
            it[id].d = d[node[l - 1]] + d[root] - 2 * d[lca(node[l - 1], root)];
            return;
        }
        int mid = l + r >> 1;
        init(id << 1, l, mid);
        init(id << 1 | 1, mid + 1, r);

    }
    void push(int id){
        long long &z = lz[id];
        if(z == 0) return;
        FOR(v, id << 1, id << 1 | 1){
            it[v].d += z;
            it[v].answer += z;
            lz[v] += z;
        }
        z = 0;
    }
    void modifyChange(int id, int l, int r, int p){
        if(l == r){
            it[id].state ^= 1;
            if(it[id].state) it[id].answer = it[id].d;
            else it[id].answer = infll;
            return;
        }
        int mid = l + r >> 1;
        push(id);
        if(p <= mid)modifyChange(id << 1, l, mid, p);
        else modifyChange(id << 1 | 1, mid + 1, r, p);
        it[id] = it[id << 1] + it[id << 1 | 1];
    }
    void modifyRange(int id, int l,int r, int u, int v, int w){
        if(l > v || r < u) return;
        if(l >= u && r <= v){
            it[id].d += w;
            it[id].answer += w;
            minimizell(it[id].answer, infll);
            lz[id] += w;
            return;
        }
        int mid = l + r >> 1;
        push(id);
        modifyRange(id << 1, l, mid, u, v, w);
        modifyRange(id << 1 | 1, mid + 1, r, u, v, w);
        it[id] = it[id << 1] + it[id << 1 | 1];
    }
    long long getDepth(int id, int l, int r, int p){
        if(l == r) return it[id].d;
        int mid = l + r >> 1;
        push(id);
        if(p <= mid) return getDepth(id << 1, l, mid, p);
        else return getDepth(id << 1 | 1, mid + 1, r, p);
    }
}tree[maxN];
bool cmp(const int &a, const int &b){
    return in[a] < in[b];
}
int lower_bound(vector<int> &v, int val){
    int l = 0, r = v.size() - 1;
    int res = v.size();
    while(l <= r){
        int mid = l + r >> 1;
        if(in[v[mid]] >= val){
            res = mid;
            r = mid - 1;
        }else l = mid + 1;
    }
    return ++res;
}
int upper_bound(vector<int> &v, int val){
    int l = 0, r = v.size() - 1, res = v.size();
    while(l <= r){
        int mid = l + r >> 1;
        if(in[v[mid]] > val){
            res = mid;
            r = mid - 1;
        }else l = mid + 1;
    }
    return ++res;
}
long long ask(int u){
    long long answer = infll;
    int cur = u;
    while(cur <= n){
        int p = lower_bound(tree[cur].node, in[u]);
        minimizell(answer, tree[cur].getDepth(1, 1, tree[cur].numNode, p) + tree[cur].it[1].answer);
        cur = par[cur];
    }
    return answer > lim ? -1 : answer;
}
void changeState(int u){
    int cur = u;
    while(cur <= n){
        int p = lower_bound(tree[cur].node, in[u]);
        tree[cur].modifyChange(1, 1, tree[cur].numNode, p);
        cur = par[cur];
    }
}
void path(int u, int w){
    int cur = u;
    while(cur <= n){
        int l = lower_bound(tree[cur].node, in[u]);
        int r = upper_bound(tree[cur].node, out[u]);
        --r;
        if(l <= r && r <= tree[cur].numNode){
            tree[cur].modifyRange(1, 1, tree[cur].numNode, l, r, w);
        }
        cur = par[cur];
    }
}
void process(){
    cin >> n >> q;
    FOR(i, 2, n){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    dfsLca();
    FOR(i, 2, cnt)lg[i] = lg[i >> 1] + 1;
    FOR(i, 1, cnt)min_depth[0][i] = tour[i];
    FOR(j, 1, lg[cnt])FOR(i, 1, cnt - (1 << j) + 1)min_depth[j][i] = getMin(min_depth[j - 1][i], min_depth[j - 1][i + (1 << (j - 1))]);
    build();
    FOR(u, 1, n){
        int cur = u;
        while(cur <= n){
            tree[cur].node.emplace_back(u);
            cur = par[cur];
        }
    }
    FOR(i, 1, n)sort(all(tree[i].node), cmp);
    FOR(i, 1, n){
        tree[i].reSize(tree[i].node.size());
        tree[i].root = i;
        tree[i].init(1, 1, tree[i].numNode);

    }
    while(q--){
        int t;
        cin >> t;
        if(t == 1){
            int u;
            cin >> u;
            cout << ask(u) << '\n';
        }else if(t == 2){
            int u;
            cin >> u;
            changeState(u);
        }else{
            int a, b, w;
            cin >> a >> b >> w;
            int u = depth[a] < depth[b] ? b : a;
            path(u, w - val[u]);
            val[u] = w;
        }
    }
}
#define NAME "grapevine"
int main(){
//    if(fopen(NAME".inp", "r")){
//        freopen(NAME".inp", "r", stdin);
//        freopen(NAME".out", "w", stdout);
//    }
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
//    cin >> t;
    while(t--)
        process();
//    cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" ;
    return 0;
}

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

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