Submission #909525

#	Time	Username	Problem	Language	Result	Execution time	Memory
909525		lighton	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	5025 ms	172368 KiB

diameter

#include<bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
int N,Q; ll W;
struct Seg{
    vector<ll> arr,lazy;
    void init(int siz){
        forf(i,1,4*siz+1){
            arr.push_back(0); lazy.push_back(0);
        }
    }
    void propagate(int now, int s, int e){
        if(lazy[now]){
            arr[now] += lazy[now];
            if(s!=e){ lazy[now*2+1] += lazy[now]; lazy[now*2] += lazy[now]; }
            lazy[now] = 0;
        }
    }
    void update(int now, int s, int e, int l, int r, ll v){
        propagate(now,s,e);
        if(l<=s && e<=r){
            arr[now] += v;
            if(s!=e){ lazy[now*2] += v; lazy[now*2+1] += v;}
            return;
        }
        if(e<l || s>r) return;
        int m = s+e>>1;
        update(now*2,s,m,l,r,v); update(now*2+1,m+1,e,l,r,v);
        arr[now] = max(arr[now*2],arr[now*2+1]);
    }
    ll query(int now, int s, int e, int l, int r){
        propagate(now,s,e);
        if(l<=s && e<=r) return arr[now];
        if(e<l || s>r) return 0;
        int m = s+e>>1;
        return max(query(now*2,s,m,l,r),query(now*2+1,m+1,e,l,r));
    }
} seg[100001];
pair<int, int> edge[100001];
ll edgev[100001];
vector<int> adj[100001];
int CENT;

//cent
int chk[100001];
int sz[100001];
int par[100001] , d[100001] , siz[100001];
vector<int> son[100001] ,soncent[100001];
int getsz(int now, int p = -1){
    sz[now] = 1;
    for(int &i : adj[now]) if(i!=p && !chk[i]) sz[now] += getsz(i,now);
    return sz[now];
}
int getcent(int now, int cap, int p = -1){
    for(int &i : adj[now]) if(i!=p && !chk[i] && 2*sz[i] > cap) return getcent(i,cap,now);
    return now;
}
int centdecom(int now, int p = -1 ,int dep = 0){
    int cent = getcent(now,getsz(now));
    par[cent] = p; d[cent] = dep; chk[cent] = 1; siz[cent] = sz[now];

    for(int &i : adj[cent]){
        if(chk[i]) continue;
        int there = centdecom(i,cent,dep+1);
        son[cent].push_back(i);
        soncent[cent].push_back(there);
    }
    return cent;
}

//ett
int in[20][100001], out[20][100001];
int sidecount[100001];
int side[20][100001];
vector<ll> sidemax[100001];
int ord;
void dfsord(int st ,int now, int dep, int p = -1, int s = -1){
    in[dep][now] = ++ord;
    side[dep][now] = s;
    for(int i : adj[now]){
        if(i==p || d[i] < dep) continue;
        if(now == st) dfsord(st,i,dep,now,++s);
        else dfsord(st,i,dep,now,s);
    }
    sidecount[st] = s;
    out[dep][now] = ord;
}

multiset<ll> ms[100001];
multiset<ll> ansset;

void init(){
    CENT = centdecom(1);

    forf(i,1,N){
        seg[i].init(siz[i]);
        ord=  0;
        dfsord(i,i,d[i]);
        forf(j,0,sidecount[i]) ms[i].insert(0);
        ansset.insert(0);
        sidemax[i].resize(sidecount[i]+1,0);
    }
}

ll ans = 0;

ll ansv(int now){
    if (ms[now].size() == 1) return *ms[now].begin();
    else {
        auto it = ms[now].begin();
        ll ret = *it;
        it++; ret += *it;
        return ret;
    }
}

void upd(int now1, int now2,  ll delta){
    int nowd = 0;
    int nowc = CENT;

    while(siz[nowc] > 1) {
        if(min(d[now1],d[now2]) < nowd) break;
        int now = now1;
        if(in[nowd][now2] > in[nowd][now1]) now = now2;
        seg[nowc].update(1, 1, siz[nowc], in[nowd][now], out[nowd][now], delta);

        int s = side[nowd][now];
        int tmp = son[nowc][s];

        ansset.erase(ansset.find(ansv(nowc)));
        ms[nowc].erase(ms[nowc].find(-sidemax[nowc][s]));
        sidemax[nowc][s] = seg[nowc].query(1, 1, siz[nowc], in[nowd][tmp], out[nowd][tmp]);
        ms[nowc].insert(-sidemax[nowc][s]);
        ansset.insert(ansv(nowc));

        nowc = soncent[nowc][s];
        nowd++;
    }
    int trash = 0;
}



int main(){
    scanf("%d %d %lld" , &N, &Q,&W);
    forf(i,0,N-2){
        int u,v; scanf("%d %d %lld" , &u,&v,&edgev[i]);
        edge[i] = {u,v};
        adj[u].push_back(v); adj[v].push_back(u);
    }

    init();

    forf(i,0,N-2){
        upd(edge[i].first, edge[i].second,edgev[i]);
    }

    ll last = 0;
    while(Q--){
        ll x; ll v; scanf("%lld %lld" , &x,&v);
        x+=last; x%=(N-1);
        v+=last; v%=W;
        ll delta = v-edgev[x];
        edgev[x] = v;
        upd(edge[x].first,edge[x].second,delta);
        ans = - *ansset.begin();
        last = ans;
        printf("%lld\n" , last);
    }
}

Compilation message (stderr)

diameter.cpp: In member function 'void Seg::update(int, int, int, int, int, ll)':
diameter.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         int m = s+e>>1;
      |                 ~^~
diameter.cpp: In member function 'll Seg::query(int, int, int, int, int)':
diameter.cpp:37:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         int m = s+e>>1;
      |                 ~^~
diameter.cpp: In function 'void upd(int, int, ll)':
diameter.cpp:141:9: warning: unused variable 'trash' [-Wunused-variable]
  141 |     int trash = 0;
      |         ^~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:147:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |     scanf("%d %d %lld" , &N, &Q,&W);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:149:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         int u,v; scanf("%d %d %lld" , &u,&v,&edgev[i]);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:162:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         ll x; ll v; scanf("%lld %lld" , &x,&v);
      |                     ~~~~~^~~~~~~~~~~~~~~~~~~~~

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