제출 #276250

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

diameter

#include <bits/stdc++.h>
#define ff first
#define ss second
#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;
    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: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27