Submission #1109385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109385		koukirocks	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	161 ms	106424 KiB

diameter

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

void dfs(int v,int p,ll dep,vvector<pll> &G,vector<ll> &ddp,vector<pll> &dfn) {
    dfn[v].F=ddp.size();
    ddp.push_back(dep);
    for (auto [i,w]:G[v]) {
        if (i==p) continue;
        dfs(i,v,dep+w,G,ddp,dfn);
        ddp.push_back(dep);
    }
    dfn[v].S=ddp.size()-1;
}

struct Node {
    ll l,r;
    ll ans;
    ll la,ra;
    ll mn,mx;
    Node *lft,*rt;
    ll lz;
    void pu() {
        ans = max({lft->ans,rt->ans,lft->ra+rt->mx,lft->mx+rt->la});
        la = max({lft->la,rt->la,rt->mx-2*lft->mn});
        ra = max({rt->ra,lft->ra,lft->mx-2*rt->mn});
        mn = min(lft->mn,rt->mn);
        mx = max(lft->mx,rt->mx);
    }
    void pd() {
        lft->lz+=lz;
        lft->la-=lz;
        lft->ra-=lz;
        lft->mx+=lz;
        lft->mn+=lz;
        rt->lz+=lz;
        rt->la-=lz;
        rt->ra-=lz;
        rt->mx+=lz;
        rt->mn+=lz;
        lz=0;
    }
    Node(ll l,ll r,vector<ll> &ddp):l(l),r(r),lz(0){
        if (l==r) {
            ans=0;
            la=-ddp[l];
            ra=-ddp[l];
            mn=ddp[l];
            mx=ddp[l];
            return;
        }
        ll mid=l+r>>1;
        lft = new Node(l,mid,ddp);
        rt = new Node(mid+1,r,ddp);
        pu();
        // cout<<l<<" "<<r<<" "<<ans<<" "<<la<<" "<<ra<<" "<<mx<<" "<<mn<<" lr ans lra mx mn\n";
    }
    void update(int L,int R,int val) {
        if (L<=l and r<=R) {
            lz+=val;
            la-=val;
            ra-=val;
            mx+=val;
            mn+=val;
            return ;
        }
        pd();
        int mid=l+r>>1;
        if (L<=mid) lft->update(L,R,val);
        if (R>=mid+1) rt->update(L,R,val);
        pu();
    }
};

int main() {
    speed;
    ll n,q,W;
    cin>>n>>q>>W;
    vvector<pll> G(n+1);
    vector<pair<pll,ll>> E(n);
    vector<ll> ddp;
    vector<pll> dfn(n+1);
    for (int i=1;i<=n-1;i++) {
        ll a,b,w;
        cin>>a>>b>>w;
        E[i]={{a,b},w};
        G[a].emplace_back(b,w);
        G[b].emplace_back(a,w);
    }
    ddp.push_back(0);
    dfs(1,0,0,G,ddp,dfn);
    // for (int i=1;i<=2*n-1;i++) cout<<ddp[i]<<' ';
    // cout<<"ddp\n";
    Node *rt = new Node(1,2*n-1,ddp);
    int last=0;
    while (q--) {
        ll d,e;
        cin>>d>>e;
        d = (d+last)%(n-1)+1;
        e = (e+last)%W;
        auto [a,b] = E[d].F;
        if (dfn[a].F>dfn[b].F) swap(a,b);
        rt->update(dfn[b].F,dfn[b].S,e-E[d].S);
        E[d].S=e;
        last=rt->ans;
        cout<<last<<"\n";
    }
    return 0;
}

/*
10 10 10000
1 9 1241
5 6 1630
10 5 1630
2 6 853
10 1 511
5 3 760
8 3 1076
4 10 2051
7 10 40
*/

Compilation message (stderr)

diameter.cpp: In constructor 'Node::Node(ll, ll, std::vector<long long int>&)':
diameter.cpp:73:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         ll mid=l+r>>1;
      |                ~^~
diameter.cpp: In member function 'void Node::update(int, int, int)':
diameter.cpp:89:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         int mid=l+r>>1;
      |                 ~^~

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