Submission #1110940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110940		guagua0407	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	211 ms	67264 KiB

diameter

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=2e5+5;
vector<pair<int,ll>> adj[mxn];
int ord[mxn];
int st[mxn];
int en[mxn];
ll depth[mxn];
int timer=0;

struct node{
    ll mn,mx,left,right,res;
};

vector<node> segtree(mxn*4);
vector<ll> lazy(mxn*4);

void dfs(int v,int p=0){
    st[v]=timer;
    ord[timer++]=v;
    for(auto u:adj[v]){
        if(u.f==p) continue;
        depth[u.f]=depth[v]+u.s;
        dfs(u.f,v);
        ord[timer++]=v;
    }
    en[v]=timer-1;
}

node comb(node L,node R){
    node ans;
    ans.mn=min(L.mn,R.mn);
    ans.mx=max(L.mx,R.mx);
    ans.left=max({L.left,R.left,L.mx-R.mn*2});
    ans.right=max({L.right,R.right,R.mx-L.mn*2});
    ans.res=max({L.res,R.res,L.left+R.mx,L.mx+R.right});
    return ans;
}

void push(int v){
    ll val=lazy[v];
    if(val==0) return;
    segtree[v*2].mn+=val;
    segtree[v*2].mx+=val;
    segtree[v*2].left-=val;
    segtree[v*2].right-=val;
    segtree[v*2+1].mn+=val;
    segtree[v*2+1].mx+=val;
    segtree[v*2+1].left-=val;
    segtree[v*2+1].right-=val;
    lazy[v*2]+=val;
    lazy[v*2+1]+=val;
    lazy[v]=0;
}

void build(int l=0,int r=timer-1,int v=1){
    if(l==r){
        int x=ord[l];
        segtree[v]={depth[x],depth[x],-depth[x],-depth[x],0};
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,v*2);
    build(mid+1,r,v*2+1);
    segtree[v]=comb(segtree[v*2],segtree[v*2+1]);
}

void update(int tl,int tr,ll val,int l=0,int r=timer-1,int v=1){
    if(r<tl or tr<l){
        return;
    }
    if(tl<=l and r<=tr){
        segtree[v].mn+=val;
        segtree[v].mx+=val;
        segtree[v].left-=val;
        segtree[v].right-=val;
        lazy[v]+=val;
        return;
    }
    push(v);
    int mid=(l+r)/2;
    update(tl,min(mid,tr),val,l,mid,v*2);
    update(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
    segtree[v]=comb(segtree[v*2],segtree[v*2+1]);
}

int main() {_
    int n,q;
    ll w;
    cin>>n>>q>>w;
    struct edge{
        int a,b;
        ll c;
    };
    vector<edge> E;
    for(int i=0;i<n-1;i++){
        int a,b;
        ll c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
        E.push_back({a,b,c});
    }
    dfs(1);
    build();
    for(int i=0;i<n-1;i++){
        if(depth[E[i].a]>depth[E[i].b]) swap(E[i].a,E[i].b);
    }
    ll last=0;
    for(int i=0;i<q;i++){
        ll d,e;
        cin>>d>>e;
        d=(d+last)%(n-1);
        e=(e+last)%w;
        int v=E[d].b;
        update(st[v],en[v],e-E[d].c);
        E[d].c=e;
        last=segtree[1].res;
        cout<<last<<'\n';
    }
    return 0;
}
//maybe its multiset not set
//yeeorz
//diaoborz

Compilation message (stderr)

diameter.cpp: In function 'void setIO(std::string)':
diameter.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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