Submission #235280

#	Time	Username	Problem	Language	Result	Execution time	Memory
235280		2fat2code	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	439 ms	47208 KiB

diameter

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define int long long
#define mp make_pair
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int nmax=100005;

int n,q,w,weight[nmax],first[nmax],last[nmax],last_ans,ans;
vector<pair<int,int>>nod[nmax];
vector<int>path;

void DFS(int s,int par){
    for(auto it:nod[s]){
        if(it.fr!=par){
            path.push_back(it.sc);
            DFS(it.fr,s);
            path.push_back(it.sc);
        }
    }
}

struct tree{
    int last,max_abc,max_a,max_bc,max_ab,max_b;
}aint[8*nmax];

tree merge(tree a,tree b){
    tree ANS;
    ANS.last=(a.last+b.last);
    ANS.max_abc=max({a.max_abc,a.max_a+b.max_bc-a.last,a.max_ab+b.max_a+a.last,b.max_abc});
    ANS.max_a=max({a.max_a,b.max_a+a.last});
    ANS.max_bc=max({a.max_bc,a.max_b+b.max_a+a.last,b.max_bc-a.last});
    ANS.max_ab=max({a.max_ab,a.max_a+b.max_b-2*a.last,b.max_ab-a.last});
    ANS.max_b=max({a.max_b,b.max_b-2*a.last});
    return ANS;
}

void update(int l,int r,int pos,int nod){
    if(l==r){
        int curr=weight[path[pos-1]];
        if(first[path[pos-1]]==pos) aint[nod]={ curr,curr,curr,curr,0,0};
        if(last[path[pos-1]]==pos)  aint[nod]={-curr,curr,0,curr,curr,2*curr};
    }
    else{
        int mid=l+(r-l)/2;
        if(pos<=mid) update(l,mid,pos,2*nod);
        else update(mid+1,r,pos,2*nod+1);
        aint[nod]=merge(aint[2*nod],aint[2*nod+1]);
    }
}


int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    cin >> n >> q >> w;
    for(int i=1;i<n;i++){
        int x,y,z;
        cin >> x >> y >> z;
        nod[x].push_back({y,i});
        nod[y].push_back({x,i});
        weight[i]=z;
    }
    DFS(1,-1);
    for(int i=0;i<path.size();i++){
        last[path[i]]=(i+1);
        if(first[path[i]]==0) first[path[i]]=(i+1);
    }
    for(int i=1;i<=2*n-2;i++){
        update(1,2*n-2,i,1);
    }
    for(int i=1;i<=q;i++){
        int x,y;
        cin >> x >> y;
        x=(x+last_ans)%(n-1)+1;
        y=(y+last_ans)%w;
        weight[x]=y;
        update(1,2*n-2,first[x],1);
        update(1,2*n-2,last[x],1);
        last_ans=aint[1].max_abc;
        cout << last_ans << '\n';
    }
}

Compilation message (stderr)

diameter.cpp: In function 'int32_t main()':
diameter.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<path.size();i++){
                 ~^~~~~~~~~~~~

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