제출 #276776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
276776		Atill83	Dynamic Diameter (CEOI19_diameter)	C++14	49 / 100	5081 ms	320836 KiB

diameter

    #include <bits/stdc++.h>
    #define ff first
    #define ss second
    #pragma GCC optimize("O3")
    #define endl '\n'
    using namespace std;
    const long long INF = (long long) 1e18;
    const int mod = (int) 1e9+7;
    const int MAXN = (int) 1e5+5;
     
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;
    ll n, q, w;
    vector<pll> adj[MAXN];
    struct ed{
        ll a, b, c;
    } egs[MAXN];
     
    int kacc[MAXN]; // i. node kaçıncı centroid
    int preC[MAXN]; //i. node centroid olmadan önce hangi node centroiddi
    int sz[MAXN]; // subtree size'ı
     
    struct yap{
        int center, size;
        multiset<ll> mx;
        multiset<ll> subans;
        vector<ll> t;
        vector<ll> lazy;
        unordered_map<int, int> tin, tout;
        vector<ll> der;
        vector<int> bpar;
        ll ans;
        int cnt;
     
        void build(int v, int l, int r){
            if(l == r){
                t[v] = der[l];
                lazy[v] = 0;
            }else{
                int m = (l + r) / 2;
                build(2*v, l, m);
                build(2*v+1, m + 1, r);
                t[v] = max(t[2*v], t[2*v + 1]);
                lazy[v] = 0;
            }
        }
     
        void push(int v){
            lazy[2*v] += lazy[v];
            lazy[2*v+1] += lazy[v];
            t[2*v] += lazy[v];
            t[2*v+1] += lazy[v];
            lazy[v] = 0;
        }
     
        void upd(int v, int tl, int tr, int l, int r, ll val){
            if(l > r) return;
            else if(tl == l && tr == r){
                t[v] += val;
                lazy[v] += val;
            }else{
                push(v);
                int tm = (tl + tr) / 2;
                upd(2*v, tl ,tm, l, min(tm, r), val);
                upd(2*v+1, tm + 1, tr, max(tm + 1, l), r, val);
                t[v] = max(t[2*v], t[2*v + 1]);
            }
        }
     
        ll que(int v, int tl, int tr, int l, int r){
            if(l > r) return 0;
            else if(tl == l && tr == r){
                return t[v];
            }else{
                push(v);
                int tm = (tl + tr) / 2;
                return max(que(2*v, tl, tm, l, min(tm, r)),
                           que(2*v+1, tm + 1, tr, max(tm  + 1, l), r));
            }
        }
     
        void dfs1(int v, int par){
            int sim = cnt++;
            tin[v] = sim;
            for(pll u: adj[v]){
                int j = u.ff;
                if(j == par || kacc[j] < kacc[center]) continue;
                der[cnt] = der[sim] + u.ss,
                dfs1(j, v);
            }
            tout[v] = cnt - 1;
        }
     
        void dfs2(int v, int par){
            for(pll u: adj[v]){
                int j = u.ff;
                if(j == par || kacc[j] < kacc[center]) continue;
                bpar[tin[j]] = bpar[tin[v]];
                dfs2(j, v);
            }
        }
     
     
        ll gt(){
            ll ansi1 = (subans.empty() ? 0 : *subans.rbegin());
            if(mx.empty()) return ansi1;
            auto ite = mx.rbegin();
            ll ansi = 0;
            ansi += *ite;
            ite++;
            if(ite == mx.rend()) return max(ansi1, ansi);
            else return max(ansi1, ansi + *ite);
        }
     
        void init(int node){
            center = node;
            size = sz[center] + 1;
            t.resize(4*size + 5);
            lazy.resize(4*size + 5);
            der.resize(size);
            bpar.resize(size);
            der[1] = 0;
            bpar[1] = -1;
            cnt = 1;
            dfs1(center, -1);
            for(pll u: adj[center]){
                int j = u.ff;
                if(kacc[j] < kacc[center]) continue;
                bpar[tin[j]] = j;
                dfs2(j, center);
            }
            //cerr<<center<<" "<<size<<" "<<cnt<<endl;
            assert(size == cnt);
            build(1, 1, size - 1);
     
            for(pii u: adj[center]){
                int j = u.ff;
                if(kacc[j] < kacc[center]) continue;
                mx.insert(que(1, 1, size - 1, tin[j], tout[j]));
            }
     
            ans = gt();
        }
     
        ll op(int idx, ll val){
            if(mx.empty()) return 0;
            int u = egs[idx].a, v = egs[idx].b;
            ll dif = val - egs[idx].c;
            int uu = tin[u], vv = tin[v];
            if(uu > vv){
                swap(u, v);
                swap(uu, vv);
            }
            auto ali = mx.lower_bound(que(1, 1, size - 1, tin[bpar[vv]], tout[bpar[vv]]));
            
            assert(ali != mx.end());
            mx.erase(ali);
            upd(1, 1, size - 1, vv, tout[v], dif);
            mx.insert(que(1, 1, size - 1, tin[bpar[vv]], tout[bpar[vv]]));
            ans = gt();
            return ans;
        }
     
     
    } yapi[MAXN];
     
    void dfs(int v, int par, int kc){
        sz[v] = 1;
        for(pll u: adj[v]){
            int j = u.ff; 
            if(j == par || (kacc[j] != 0 && kacc[j] <= kc)) continue;
            dfs(j, v, kc);
            sz[v] += sz[j];
        }
    }
     
    int find_centro(int v, int kc){
        int cur = v;
        int last = -1;
        dfs(v, -1, kc);
        bool tru = 1;
     
        while(tru){
            tru = 0;
            for(pll u: adj[cur]){
                int j = u.ff;
                if(j == last || (kacc[j] != 0 && kacc[j] <= kc)) continue;
                if(sz[j] > sz[v] / 2){
                    last = cur;
                    cur = j;
                    tru = 1;
                    break;
                }
            }
        }
        return cur;
    }
     
    void decomp(int v, int kc, int onc){
        int centro = find_centro(v, kc);
        kacc[centro] = kc;
        preC[centro] = onc;
        sz[centro] = sz[v];
        for(pll u: adj[centro]){
            int j = u.ff;
            if(kacc[j] != 0 && kacc[j] < kc) continue;
            decomp(j, kc + 1, centro);
        }
    }
     
     
    int sira[MAXN];
     
     
    int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);cout.tie(nullptr);
     
        #ifdef Local
            freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
            freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
        #endif
     
        cin>>n>>q>>w;
     
        for(int i = 0; i < n - 1; i++){
            ll a, b, c;
            cin>>a>>b>>c;
            adj[a].push_back({b, c});
            adj[b].push_back({a, c});
            egs[i] = {a, b, c};
        }
     
        decomp(1, 1, -1);
     
        // initle
        for(int i = 1; i <= n; i++){
            sira[i] = i;
        }
     
        sort(sira + 1, sira + n + 1, [](int a, int b) {
            return kacc[a] > kacc[b];
        });
     
        for(int i = 1; i <= n; i++){
            yapi[sira[i]].init(sira[i]);
            int cur = sira[i];
            if(preC[cur] != -1){
                yapi[preC[cur]].subans.insert(yapi[cur].ans);
            }
        }
     
     
        ll last = 0;
        for(int i = 0; i < q; i++){
            ll d, e;
            cin>>d>>e;
        
            d = (d - (n - 1) + last%(n - 1))%(n - 1);
            e = (e - w + last%w)%w;
            if(d < 0) d += n - 1;
            if(e < 0) e += w;
            int u = egs[d].a, v = egs[d].b;
            if(kacc[u] > kacc[v])
                swap(u, v);
            int cur = u;
            ll ans = yapi[v].gt();
            while(cur != -1){
                if(preC[cur] != -1){
                    auto s = yapi[preC[cur]].subans.lower_bound(yapi[cur].ans);
                    yapi[preC[cur]].subans.erase(s);
                }
     
                ans = max(ans, yapi[cur].op(d, e));
                if(preC[cur] != -1){
                    yapi[preC[cur]].subans.insert(yapi[cur].ans);
                }
                cur = preC[cur];
            }
            cout<<ans<<endl;
            last = ans;
            egs[d].c = e;
            //islemi yaptıktan sonra egs'de weighti updatele!!!!!
     
        }
     
        #ifdef Local
            cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
        #endif
    }

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27