Submission #909345

#	Time	Username	Problem	Language	Result	Execution time	Memory
909345		lighton	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	260 ms	34576 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;

pair<int, int> edge[100001];
ll edgev[100001];
vector<int> adj[100001];
int in[100001], out[100001];
int sidecount,sidenum[100001], side[100001];
int ord;
void dfsord(int now, int p = -1, int s = -1){
    in[now] = ++ord;
    side[now] = s;
    for(int i : adj[now]){
        if(i==p)continue;
        if(now == 1){
            sidenum[++s] = i;
            dfsord(i,now,s);
        }
        else dfsord(i,now,s);
    }
    sidecount = s;
    out[now] = ord;
}

multiset<ll> ms;
ll sidemax[100001];
void upd(int now, ll delta){
    seg.update(1,1,N,in[now],out[now],delta);
    ms.erase(ms.find(-sidemax[side[now]]));

    int tmp = sidenum[side[now]];
    sidemax[side[now]] = seg.query(1,1,N,in[tmp],out[tmp]);
    ms.insert(-sidemax[side[now]]);
}
ll ans(){
    if(ms.size() == 1) return - *ms.begin();
    else{
        auto it = ms.begin();
        ll ret = - *it;
        it++; ret-=*it;
        return ret;
    }
}

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);
    }

    dfsord(1);
    seg.init(N);
    forf(i,0,sidecount) ms.insert(0);
    forf(i,0,N-2){
        int now = edge[i].first;
        if(in[edge[i].second] > in[edge[i].first]) now = edge[i].second;
        upd(now,edgev[i]);
    }

    ll last = 0;
    while(Q--){
        int x; ll v; scanf("%d %lld" , &x,&v);
        x+=last; x%=(N-1);
        v+=last; v%=W;
        int now = edge[x].first;
        if(in[edge[x].second] > in[edge[x].first]) now = edge[x].second;
        ll delta = v-edgev[x];
        edgev[x] = v;
        upd(now,delta);
        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 'int main()':
diameter.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%d %d %lld" , &N, &Q,&W);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:86:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         int u,v; scanf("%d %d %lld" , &u,&v,&edgev[i]);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:102:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         int x; ll v; scanf("%d %lld" , &x,&v);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~

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