Submission #909345

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
909345	2024-01-17T07:25:51 Z	lighton	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	260 ms	34576 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	4952 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	4952 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4952 KB	Output is correct
2	Correct	2 ms	5132 KB	Output is correct
3	Correct	3 ms	4988 KB	Output is correct
4	Correct	10 ms	4980 KB	Output is correct
5	Correct	48 ms	5876 KB	Output is correct
6	Correct	2 ms	4956 KB	Output is correct
7	Correct	2 ms	4956 KB	Output is correct
8	Correct	2 ms	4956 KB	Output is correct
9	Correct	4 ms	4956 KB	Output is correct
10	Correct	14 ms	5112 KB	Output is correct
11	Correct	62 ms	6368 KB	Output is correct
12	Correct	6 ms	5848 KB	Output is correct
13	Correct	6 ms	6100 KB	Output is correct
14	Correct	10 ms	6104 KB	Output is correct
15	Correct	22 ms	6136 KB	Output is correct
16	Correct	90 ms	7120 KB	Output is correct
17	Correct	107 ms	23216 KB	Output is correct
18	Correct	123 ms	22356 KB	Output is correct
19	Correct	120 ms	22356 KB	Output is correct
20	Correct	193 ms	23876 KB	Output is correct
21	Correct	260 ms	24312 KB	Output is correct