제출 #1170251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170251		nathan4690	Grapevine (NOI22_grapevine)	C++20	100 / 100	908 ms	168032 KiB

Main

// Cay nho - GRAPE
// NOI Singapore 2022 Task 4: Grapevine
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn=1e5+5, inf=1e16;

struct Lazy{
    long long data = 0;
    Lazy(){};
    Lazy(long long data): data(data){};
    Lazy operator+(const Lazy &rhs) const{
        // Push a lazy down
        return Lazy(data + rhs.data);
    }
};

struct Value{
    long long data = 1e18;
    Value(){};
    Value(long long data): data(data){};
    Value operator+(const Value &rhs) const{
        // Merge two nodes
        return Value(min(data, rhs.data));
    }
    Value operator+(const Lazy &rhs) const{
        // Apply lazy to node
        return Value(data + rhs.data);
    }
};

template<class T, class U>
struct SegmentTree{
    int n;
    vector<T> st;
    vector<U> lazy;
    SegmentTree(){};
    SegmentTree(int n): n(n), st(4*n+1), lazy(4*n+1){};
    inline void down(int idx){
        st[idx*2] = st[idx*2] + lazy[idx];
        lazy[idx*2] = lazy[idx*2] + lazy[idx];
        st[idx*2+1] = st[idx*2+1] + lazy[idx];
        lazy[idx*2+1] = lazy[idx*2+1] + lazy[idx];
        lazy[idx] = U();
    }
    void _upd1(int idx, int l, int r, int i, const T &v){
        if(i < l || r < i) return;
        if(l == r){
            st[idx] = v;
            return;
        }
        down(idx);
        int mid = (l + r) / 2;
        _upd1(idx*2, l, mid, i, v);
        _upd1(idx*2+1, mid+1, r, i, v);
        st[idx] = st[idx*2] + st[idx*2+1];
    }
    inline void updatePoint(int position, const T &value){
        _upd1(1,1,n,position,value);
    }
    void _upd2(int idx, int l, int r, int u, int v, const U &w){
        if(v < l || r < u) return;
        if(u <= l && r <= v){
            st[idx] = st[idx] + w;
            lazy[idx] = lazy[idx] + w;
            return;
        }
        down(idx);
        int mid = (l + r) / 2;
        _upd2(idx*2, l, mid, u, v, w);
        _upd2(idx*2+1, mid+1, r, u, v, w);
        st[idx] = st[idx*2] + st[idx*2+1];
    }
    inline void updateRange(int left_, int right_, const U &value){
        _upd2(1,1,n,left_, right_, value);
    }
    T _get(int idx, int l, int r, int u, int v){
        if(v < l || r < u) return T();
        if(u <= l && r <= v) return st[idx];
        down(idx);
        int mid = (l + r) / 2;
        return _get(idx*2, l, mid, u, v) + _get(idx*2+1, mid+1, r, u, v);
    }
    inline T getRange(int left_, int right_){
        return _get(1,1,n,left_, right_);
    }
};

#define SegTree SegmentTree<Value,Lazy>

int n, q, wei[maxn];
vector<pair<int,int>> G[maxn];
map<int, int> edgeID[maxn];
bool haveGrape[maxn];

int sz[maxn], parc[maxn], depc[maxn];
bool del[maxn];

void dfs_sz(int u, int p){
    sz[u] = 1;
    for(pair<int,int> e: G[u]){
        int c = e.first;
        if(c != p && !del[c]){
            dfs_sz(c, u);
            sz[u] += sz[c];
        }
    }
}

int find_centroid(int u, int p, int N){
    for(pair<int,int> e: G[u]){
        int c = e.first;
        if(c != p && !del[c] && sz[c] > N / 2){
            return find_centroid(c, u, N);
        }
    }
    return u;
}

vector<int> sp[maxn], ep[maxn], nodes[maxn];
int timer;
SegTree st[maxn];

void build_euler(int u, int p, int root, ll cdep){
    int idx = nodes[root].size();
    nodes[root].push_back(u);
    st[root].updatePoint(timer, cdep + inf);
    sp[root].push_back(timer++);
    ep[root].push_back(0);
    for(pair<int,int> e: G[u]){
        int c = e.first, w = wei[e.second];
        if(c != p && !del[c]){
            build_euler(c, u, root, cdep + w);
        }
    }
    ep[root][idx] = timer - 1;
}

void build_cen(int u, int p = 0, int dd = 0){
    dfs_sz(u, 0);
    int root = find_centroid(u, 0, sz[u]);
    parc[root] = p;
    depc[root] = dd;
    st[root] = SegTree(sz[u]);
    timer = 1;
    build_euler(root, 0, root, 0);
    vector<pair<int,int>> tmpnode;
    for(int i=0;i<nodes[root].size();i++){
        tmpnode.push_back({nodes[root][i], i});
    }
    sort(tmpnode.begin(), tmpnode.end());
    vector<int> tmpv;
    nodes[root].clear();
    for(pair<int,int> item: tmpnode){
        nodes[root].push_back(item.first);
        tmpv.push_back(sp[root][item.second]);
    }
    swap(sp[root], tmpv);
    tmpv.clear();
    for(pair<int,int> item: tmpnode){
        tmpv.push_back(ep[root][item.second]);
    }
    swap(ep[root], tmpv);
    del[root] = true;
    for(pair<int,int> e: G[root]){
        int c = e.first;
        if(!del[c]) {
            build_cen(c, root, depc[root] + 1);
        }
    }
}

//int par[17][maxn], udep[maxn];
//ll depth[maxn];
//void binlift(int u, int p){
//    par[0][u] = p;
//    for(int i=1;i<17;i++) par[i][u] = par[i-1][par[i-1][u]];
//    for(pair<int,int> e: G[u]){
//        int c = e.first, w = wei[e.second];
//        if(c != p){
//            depth[c] = depth[u] + w;
//            udep[c] = udep[u] + 1;
//            binlift(c, u);
//        }
//    }
//}
//
//int LCA(int u, int v){
//    if(udep[u] < udep[v]) swap(u, v);
//    int l = udep[u] - udep[v];
//    for(int i=0;i<17;i++){
//        if(l >> i & 1) u = par[i][u];
//    }
//    if(u == v) return u;
//    for(int i=16;i>=0;i--){
//        if(par[i][u] != par[i][v]){
//            u = par[i][u];
//            v = par[i][v];
//        }
//    }
//    return par[0][u];
//}

ll getDist(int root, int u){
    int idx = lower_bound(nodes[root].begin(), nodes[root].end(), u) - nodes[root].begin();
    ll res = st[root].getRange(sp[root][idx], sp[root][idx]).data;
    if(!haveGrape[u]) res -= inf;
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp", "r", stdin);
        freopen(__file_name ".out", "w", stdout);
    }
    // code here
    cin >> n >> q;
    f1(i,n-1){
        int u, v, w; cin >> u >> v >> w;
        wei[i] = w;
        G[u].push_back({v, i});
        G[v].push_back({u, i});
        edgeID[u][v] = edgeID[v][u] = i;
    }
//    binlift(1, 0);
    build_cen(1);
    while(q--){
        int tp; cin >> tp;
        if(tp == 1){
            int u; cin >> u;
            ll ans = inf;
            int v = u;
            while(v != 0){
//                cout << v << " -> " << u << ' ' << ans << ' ' << getDist(v, u) << ' ' << st[v].st[1].data << '\n';
                ans = min(ans, getDist(v, u) + st[v].st[1].data);
                v = parc[v];
            }
            cout << (ans >= 1e15 ? -1LL : ans) << '\n';
        }else if(tp == 2){
            int u; cin >> u;
            int v = u;
            while(v != 0){
                int idx = lower_bound(nodes[v].begin(), nodes[v].end(), u) - nodes[v].begin();
                ll newVal = (haveGrape[u] ? inf : -inf);
                st[v].updateRange(sp[v][idx], sp[v][idx], newVal);
//                cout << "! " << v << " => " << u << ' ' << parc[v] << ' ' << newVal << '\n';
                v = parc[v];
            }
            haveGrape[u] = !haveGrape[u];
        }else{
            int u, v, w; cin >> u >> v >> w;
            int eidx = edgeID[u][v];
            ll diff = w - wei[eidx];
            wei[eidx] = w;
            if(depc[u] > depc[v]) swap(u, v);
            // move from u up
            int root = u;
            while(root != 0){
                int uidx = lower_bound(nodes[root].begin(), nodes[root].end(), u) - nodes[root].begin();
                int vidx = lower_bound(nodes[root].begin(), nodes[root].end(), v) - nodes[root].begin();
                if(sp[root][vidx] <= sp[root][uidx] && ep[root][uidx] <= ep[root][vidx]){
                    swap(uidx, vidx);
                }
                // u is parent of v in root
                st[root].updateRange(sp[root][vidx], ep[root][vidx], diff);
                root = parc[root];
            }
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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