Submission #1261253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261253		minhpk	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	258 ms	83356 KiB

diameter

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 200005;
const int INF  = (int)1e16;

int a,q,sadge;
vector<pair<int,int>> z[maxn];
int high[maxn];
int sta[maxn], fin[maxn], euler[3*maxn], tour=0;
int depth[1000005];
int par[300001][21];
bool cmp(pair<int,int> a,pair<int,int> b){
     return a.second<b.second;
}
void dfs(int u, int p){
    sta[u] = ++tour;
    par[u][0]=p;
    euler[tour] = u;
    for(auto &pr: z[u]){
        int v = pr.first, w = pr.second;
        if(v==p) continue;
        high[v] = high[u] + w;
        depth[v]=depth[u]+1;
        dfs(v, u);
        euler[++tour] = u;
    }
    fin[u] = ++tour;
    euler[tour] = u;
}
int lca1(int x,int y){
    for (int i=20;i>=0;i--){
         if (depth[par[x][i]]>depth[y]){
             x=par[x][i];
         }
    }
    return x;
}
int lca(int x,int y){
    if (depth[x]<depth[y]){
        swap(x,y);
    }
    for (int i=20;i>=0;i--){
         if (depth[par[x][i]]>=depth[y]){
             x=par[x][i];
         }
    }
    if (x==y){
        return x;
    }
    for (int i=20;i>=0;i--){
         if (par[x][i]!=par[y][i] && par[x][i]!=0){
             x=par[x][i];
             y=par[y][i];
         }
    }
    return par[x][0];
}

struct node {
    int max1, min1, lazy;
    int val, val1;
};
node f[12*maxn];


node combine(const node &A, const node &B){
    node R;

    R.max1 = max(A.max1, B.max1);
    R.min1 = min(A.min1, B.min1);
    R.lazy = 0;

    R.val  = max({ A.val, B.val, B.max1 - 2*A.min1 });

    R.val1 = max({ A.val1, B.val1, A.max1 - 2*B.min1 });
    return R;
}

void push(int id){
    if(f[id].lazy){
        int d = f[id].lazy;
        for(int ch: {id*2, id*2+1}){
            f[ch].lazy += d;
            f[ch].max1  += d;
            f[ch].min1  += d;
            f[ch].val   -= d;
            f[ch].val1  -= d;
        }
        f[id].lazy = 0;
    }
}
void build(int id, int l, int r){
    if(l==r){
        int h = high[euler[l]];
        f[id].max1 = f[id].min1 = h;
        f[id].lazy = 0;
        f[id].val  = -INF;
        f[id].val1 = -INF;
        return;
    }
    int m = (l+r)/2;
    build(id*2,   l,   m);
    build(id*2+1, m+1, r);
    f[id] = combine(f[id*2], f[id*2+1]);
}
void update(int id, int l, int r, int x, int y, int d){
    if(y<l || x>r) return;
    if(x<=l && r<=y){
        f[id].max1 += d;
        f[id].min1 += d;
        f[id].lazy += d;
        f[id].val  -= d;
        f[id].val1 -= d;
        return;
    }
    push(id);
    int m = (l+r)/2;
    update(id*2,   l,   m, x, y, d);
    update(id*2+1, m+1, r, x, y, d);
    f[id] = combine(f[id*2], f[id*2+1]);
}

node get(int id, int l, int r, int x, int y){
    if(y<l || x>r){
       return { -INF, INF, 0, -INF, -INF };
    }
    if(x<=l && r<=y){
        return f[id];
    }
    push(id);
    int m = (l+r)/2;
    return combine(
        get(id*2,   l,   m, x, y),
        get(id*2+1, m+1, r, x, y)
    );
}
int get1(int id,int l,int r,int pos){
    if (l==r){
        return f[id].max1;
    }
    int mid=(l+r)/2;
    push(id);
    if (pos<=mid){
        return get1(id*2,l,mid,pos);
    }else{
        return get1(id*2+1,mid+1,r,pos);
    }
}
int get2(int id,int l,int r,int val){
    if (l==r){
        return l;
    }
    int mid=(l+r)/2;
    push(id);
    if (f[id*2].max1==val){
        return get2(id*2,l,mid,val);
    }else{
        return get2(id*2+1,mid+1,r,val);
    }
}
struct node1{
    int x,y,t;
};
node1 edge[1000005];

vector <pair<int,int>> segment;
vector <pair<int,int>> v;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> q >> sadge;
    for(int i=1;i<a;i++){
        int x,y,t;
        cin >> x >> y >> t;
        z[x].push_back({y,t});
        z[y].push_back({x,t});
        edge[i]={x,y,t};
    }
    depth[0]=-1;
    dfs(1,0);
    build(1,1,tour);
    for (int i=1;i<a;i++){
         if (depth[edge[i].x]<depth[edge[i].y]){
             swap(edge[i].x,edge[i].y);
         }
    }
    for (int j=1;j<=20;j++){
         for (int i=1;i<=a;i++){
              par[i][j]=par[par[i][j-1]][j-1];
         }
    }
   // cout << tour << "\n";
    
    int cnt=0;
    int last=0;
    while(q--){
        int x,y;
        cin >> x >> y;
        x=(last+x)%(a-1);
        y=(last+y)%sadge;
       // cout << x << " " << y << "\n";
        x++;
        int cur=edge[x].t;
        int diff=y-cur;
        int v=edge[x].x;
        edge[x].t=y;
        update(1,1,tour,sta[v],fin[v],diff);
        int maxlen=f[1].max1;
        int pos=get2(1,1,tour,maxlen);
        int res=get(1,1,tour,1,pos).val1;
        int res1=get(1,1,tour,pos,tour).val;
        cout << max(res,res1)+maxlen << "\n";
        last=max(res,res1)+maxlen;
    }
    return 0;
}
/*
5
1 2 1
1 4 2
2 3 3
2 5 4
2

2 1 100
1 2 4 1 3 4 5

*/

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