Submission #447077

#	Time	Username	Problem	Language	Result	Execution time	Memory
447077		yungyao	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	396 ms	42412 KiB

diameter

using namespace std;
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <utility>
#include <memory.h>
#include <vector>
#include <bitset>

typedef pair<int,int> pii;
typedef long long LL;

#define iter(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#define mkp make_pair

#include <climits>
const int maxn = 1e5+100,mod = 0;

struct EDGE{
    int u,v;
    LL w;

    EDGE(int u,int v,LL w):u(u), v(v), w(w){}
    EDGE(){}
}edge[maxn];

vector <pair<int,LL>> adj[maxn];
int father[maxn];
pii seg[maxn];
LL mx[maxn];

#define mid (LB+RB)/2

struct segtree{
    vector <LL> arr,mx,lazy;
    segtree(){
        arr.resize(1);
    }

    void maketree(int cur,int LB,int RB){
        if (LB == RB) mx[cur] = arr[LB];
        else{
            maketree(cur*2,LB,mid);
            maketree(cur*2+1,mid+1,RB);
            mx[cur] = max(mx[cur*2],mx[cur*2+1]);
        }
    }

    void mt(){
        mx.resize(arr.size()*4);
        lazy.resize(arr.size()*4);
        maketree(1,1,arr.size()-1);
    }

    void push(int cur,int LB,int RB){
        if (lazy[cur]){
            mx[cur] += lazy[cur];
            if (LB != RB){
                lazy[cur*2] += lazy[cur];
                lazy[cur*2+1] += lazy[cur];
            }
            lazy[cur] = 0;
        }
    }

    void ru(int l,int r,LL val,int cur,int LB,int RB){
        push(cur,LB,RB);
        if (l == LB and r == RB){
            lazy[cur] += val;
            push(cur,LB,RB);
            return;
        }

        if (r <= mid) ru(l,r,val,cur*2,LB,mid);
        else if (l > mid) ru(l,r,val,cur*2+1,mid+1,RB);
        else{
            ru(l,mid,val,cur*2,LB,mid);
            ru(mid+1,r,val,cur*2+1,mid+1,RB);
        }
        push(cur*2,LB,mid);
        push(cur*2+1,mid+1,RB);
        mx[cur] = max(mx[cur*2],mx[cur*2+1]);
    }

    LL rq(int l,int r,int cur,int LB,int RB){
        push(cur,LB,RB);
        if (l == LB and r == RB) return mx[cur];

        if (r <= mid) return rq(l,r,cur*2,LB,mid);
        else if (l > mid) return rq(l,r,cur*2+1,mid+1,RB);
        else return max(rq(l,mid,cur*2,LB,mid),rq(mid+1,r,cur*2+1,mid+1,RB));
    }

    void upd(int l,int r,LL val){
        ru(l,r,val,1,1,arr.size()-1);
    }
    LL query(int l,int r){
        return rq(l,r,1,1,arr.size()-1);
    }
};

vector <segtree> st;
int belong[maxn],treecnt;

pii dfs(int x,int fr,LL dis,int sti){
    father[x] = fr;
    belong[x] = sti;
    pii r = {};
    if (adj[x].size() == 1){
        r = mkp(int(st[sti].arr.size()),int(st[sti].arr.size()));
        st[sti].arr.pb(dis);
    }
    else
        for (auto [i,w]:adj[x]) if (i != fr){
            if (!r.F) r = dfs(i,x,dis + w,sti); 
            else r.S = dfs(i,x,dis + w,sti).S;
        }

    seg[x] = r;
    return r;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n,q;
    LL w;

    cin >> n >> q >> w;
    for (int i=0;i<n-1;++i){
        int u,v; LL c;

        cin >> u >> v >> c;
        edge[i] = EDGE(u,v,c);
        adj[u].pb(mkp(v,c));
        adj[v].pb(mkp(u,c));
    }

    st.resize(adj[1].size());
    multiset <LL> ms;
    for (auto [i,d]:adj[1]){
        dfs(i,1,d,treecnt);
        st[treecnt].mt();
        mx[treecnt] = st[treecnt].mx[1];
        ms.insert(mx[treecnt]);

        ++treecnt;
    }

    for (int i=0;i<n-1;++i){
        if (edge[i].u == father[edge[i].v])
            swap(edge[i].u,edge[i].v);
    }

    LL last = 0;
    while (q--){
        LL d,e;

        cin >> d >> e;
        d = (last + d) % (n-1);
        e = (last + e) % w;

        LL dif = e - edge[d].w;
        int m = edge[d].u;
        edge[d].w = e;

        ms.erase(ms.find(mx[belong[m]]));
        st[belong[m]].upd(seg[m].F,seg[m].S,dif);
        mx[belong[m]] = st[belong[m]].mx[1];
        ms.insert(mx[belong[m]]);

        last = *prev(ms.end()) + (ms.size() > 1 ? *prev(prev(ms.end())) : 0);

        cout /*<< d << ' ' << e << ' '*/ << last << '\n';
    }

    return 0;
}

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