Submission #1040643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040643		anton	Dynamic Diameter (CEOI19_diameter)	C++17	18 / 100	264 ms	30148 KiB

diameter

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>

int N, Q, W;
const int MAX_N = 1e5;

vector<unordered_map<int, int>> adj;

signed main(){
    cin>>N>>Q>>W;
    adj.resize(N+1);

    vector<pii> edges;

    
    vector<int> lazy(N+1, 0);
    vector<pii> tr(N+1, {0, 0});
    auto upd =[&](int u){
        tr[u].first = max(tr[u*2].first, tr[u*2+1].first) + lazy[u];
        tr[u].second = max(max(tr[u*2].second, tr[u*2+1].second), tr[u*2].first + tr[u*2+1].first);
    };

    for(int i = 0; i<N-1; i++){
        int a, b, c;
        cin>>a>>b>>c;
        adj[a][b] = c;
        adj[b][a] = c;

        if(b<a){
            swap(a, b);
        }
        lazy[b] = c;
        tr[b].first = c;
        edges.push_back({a, b});
    }

    for(int i = N/2; i>=1; i--){
        upd(i);
    }




    
    int root =0;
    int last= 0;
    for(int i = 0; i<Q; i++){
        int d, e;
        cin>>d>>e;

        d = (d+last)%(N-1);
        e = (e +last)%W;

        int a = edges[d].first;
        int b=  edges[d].second;
        

        int delta = e-adj[a][b];

        adj[a][b] = e;
        adj[b][a] =e;

        if(a>b){
            swap(a, b);
        }
        lazy[b] += delta;
        tr[b].first += delta;

        for(int i = a; i>=1; i/=2){
            upd(i);
        }
        last = tr[1].second;
        cout<<last<<endl;
    }
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:48:9: warning: unused variable 'root' [-Wunused-variable]
   48 |     int root =0;
      |         ^~~~

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