oj.uz

Submission #909367

# Submission time Handle Problem Language Result Execution time Memory
909367 2024-01-17T07:35:06 Z lighton Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 322 ms 28660 KB 
#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--){
        ll x; ll v; scanf("%lld %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:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         ll x; ll v; scanf("%lld %lld" , &x,&v);
      |                     ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 1 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 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 4992 KB Output is correct
4 Correct 14 ms 5012 KB Output is correct
5 Correct 48 ms 5144 KB Output is correct
6 Correct 1 ms 4952 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 3 ms 4952 KB Output is correct
9 Correct 3 ms 4952 KB Output is correct
10 Correct 13 ms 4956 KB Output is correct
11 Correct 62 ms 5712 KB Output is correct
12 Correct 5 ms 5592 KB Output is correct
13 Correct 5 ms 5784 KB Output is correct
14 Correct 7 ms 5848 KB Output is correct
15 Correct 24 ms 5844 KB Output is correct
16 Correct 89 ms 6092 KB Output is correct
17 Correct 105 ms 22596 KB Output is correct
18 Correct 122 ms 21176 KB Output is correct
19 Correct 114 ms 21420 KB Output is correct
20 Correct 133 ms 21212 KB Output is correct
21 Correct 322 ms 22516 KB Output is correct

Subtask #4
0 / 18.0

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

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 19000 KB Output is correct
2 Correct 190 ms 21844 KB Output is correct
3 Correct 193 ms 21848 KB Output is correct
4 Correct 204 ms 21696 KB Output is correct
5 Correct 246 ms 22008 KB Output is correct
6 Correct 213 ms 24264 KB Output is correct
7 Correct 198 ms 24296 KB Output is correct
8 Correct 213 ms 24176 KB Output is correct
9 Correct 208 ms 23976 KB Output is correct
10 Correct 259 ms 24632 KB Output is correct
11 Correct 261 ms 24988 KB Output is correct
12 Correct 218 ms 26668 KB Output is correct
13 Correct 187 ms 28660 KB Output is correct
14 Correct 216 ms 27820 KB Output is correct
15 Correct 244 ms 27936 KB Output is correct
16 Correct 211 ms 28068 KB Output is correct
17 Correct 255 ms 28648 KB Output is correct
18 Correct 223 ms 27852 KB Output is correct
19 Correct 163 ms 28396 KB Output is correct
20 Correct 171 ms 27760 KB Output is correct
21 Correct 234 ms 28552 KB Output is correct
22 Correct 237 ms 27788 KB Output is correct
23 Correct 238 ms 28544 KB Output is correct
24 Correct 266 ms 28496 KB Output is correct

Subtask #6
0 / 27.0

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