Submission #1095616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095616		PieArmy	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3128 ms	242296 KiB

diameter

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
 
struct Seg{
    int n;
    vector<ll>mx,lazy,arr;
    void build(int node=1,int left=0,int right=-1){
        if(right==-1)right=n-1;
        if(left==right){
            mx[node]=arr[left];
            return;
        }
        build(node+1,left,mid);build(node+((mid-left+1)<<1),mid+1,right);
        mx[node]=max(mx[node+1],mx[node+((mid-left+1)<<1)]);
    }
    void push(int node,int left,int right){
        if(lazy[node]==0)return;
        mx[node]+=lazy[node];
        if(left!=right){
            lazy[node+1]+=lazy[node];
            lazy[node+((mid-left+1)<<1)]+=lazy[node];
        }
        lazy[node]=0;
    }
    void yap(vector<ll>v){
        arr=v;
        n=arr.size();
        mx.resize((n<<1)+2);
        lazy.resize((n<<1)+2,0);
        build();
    }
    int l,r;ll x;
    void up(int node=1,int left=0,int right=-1){
        if(right==-1)right=n-1;
        if(left>=l&&right<=r){
            lazy[node]+=x;
            push(node,left,right);
            return;
        }
        push(node,left,right);
        if(left>r||right<l)return;
        up(node+1,left,mid);up(node+((mid-left+1)<<1),mid+1,right);
        mx[node]=max(mx[node+1],mx[node+((mid-left+1)<<1)]);
    }
    void update(int lef,int rig,ll val){
        l=lef;r=rig;x=val;
        up();
    }
};
 
int n,q;
ll w,K[100001];
vector<pair<int,ll>>adj[100001];
map<int,pair<int,int>>in_out[100001];
multiset<ll>vals[100001];
vector<Seg>seg[100001];
int level[100001],par[100001],parnum[100001];
pair<int,int>edge[100001];
multiset<ll>bests;
// temp stuff
int sub[100001];
int tim,root;
// temp stuff
 
void dfs1(int pos,int prev){
    sub[pos]=1;
    for(auto[x,y]:adj[pos]){
        if(level[x]==0&&x!=prev){
            dfs1(x,pos);
            sub[pos]+=sub[x];
        }
    }
}
 
void dfs2(int pos,int prev,ll l,vector<ll>&v){
    v[tim]+=l;
    in_out[pos][root].fr=tim++;
    for(auto[x,y]:adj[pos]){
        if(level[x])continue;
        if(x==prev)continue;
        dfs2(x,pos,y,v);
    }
    in_out[pos][root].sc=tim;
    v[tim]-=l;
}
 
void cal(int pos,int prev,int num){
    dfs1(pos,0);
    int total=sub[pos];
    int paren=pos;
    while(true){
        int nex=0;
        for(auto[x,y]:adj[pos]){
            if(level[x]!=0||x==paren)continue;
            if(sub[x]>(total>>1)){
                nex=x;
                break;
            }
        }
        if(!nex)break;
        paren=pos;
        pos=nex;
    }
    par[pos]=prev;
    parnum[pos]=num;
    level[pos]=level[par[pos]]+1;
    seg[pos].resize(adj[pos].size());
    vals[pos].insert(0);
    vals[pos].insert(0);
    root=pos;
    in_out[pos][pos]={-1,-1};
    for(int i=0;i<adj[pos].size();i++){
        if(level[adj[pos][i].fr])continue;
        vector<ll>v(adj[pos][i].fr==paren?total-sub[pos]+1:sub[adj[pos][i].fr]+1,0);
        tim=0;
        dfs2(adj[pos][i].fr,pos,adj[pos][i].sc,v);
        for(int j=1;j<v.size();j++){
            v[j]+=v[j-1];
        }
        seg[pos][i].yap(v);
        vals[pos].insert(-seg[pos][i].mx[1]);
    }
    ll topla=-(*vals[pos].begin())-(*(++vals[pos].begin()));
    bests.insert(topla);
    for(int i=0;i<adj[pos].size();i++){
        if(level[adj[pos][i].fr])continue;
        cal(adj[pos][i].fr,pos,i);
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin>>n>>q>>w;
    for(int i=0;i<n-1;i++){
        int a,b;ll c;
        cin>>a>>b>>K[i];
        edge[i]={a,b};
        adj[a].pb({b,K[i]});
        adj[b].pb({a,K[i]});
    }
    cal(1,0,0);
    ll ans=0;
    while(q--){
        int d;ll e;
        cin>>d>>e;
        d=(d+ans)%(n-1);
        e=(e+ans)%w;
        if(level[edge[d].fr]>level[edge[d].sc])swap(edge[d].fr,edge[d].sc);
        int pos=edge[d].fr;
        int sira;
        int pos2=edge[d].sc;
        while(pos2!=pos){
            sira=parnum[pos2];
            pos2=par[pos2];
        }
        ll diff=e-K[d];
        K[d]=e;
        while(pos){
            ll topla=-(*vals[pos].begin())-(*(++vals[pos].begin()));
            bests.erase(bests.find(topla));
            vals[pos].erase(vals[pos].find(-seg[pos][sira].mx[1]));
            int cur=edge[d].fr;
            if(in_out[cur][pos].fr<in_out[edge[d].sc][pos].fr)cur=edge[d].sc;
            seg[pos][sira].update(in_out[cur][pos].fr,in_out[cur][pos].sc-1,diff);
            vals[pos].insert(-seg[pos][sira].mx[1]);
            topla=-(*vals[pos].begin())-(*(++vals[pos].begin()));
            bests.insert(topla);
            sira=parnum[pos];
            pos=par[pos];
        }
        ans=*(--bests.end());
        cout<<ans<<endl;
    }
}

Compilation message (stderr)

diameter.cpp: In function 'void cal(int, int, int)':
diameter.cpp:122:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for(int i=0;i<adj[pos].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
diameter.cpp:127:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for(int j=1;j<v.size();j++){
      |                     ~^~~~~~~~~
diameter.cpp:135:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(int i=0;i<adj[pos].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:145:20: warning: unused variable 'c' [-Wunused-variable]
  145 |         int a,b;ll c;
      |                    ^
diameter.cpp:171:58: warning: 'sira' may be used uninitialized in this function [-Wmaybe-uninitialized]
  171 |             vals[pos].erase(vals[pos].find(-seg[pos][sira].mx[1]));
      |                                                          ^

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