Submission #779501

#	Time	Username	Problem	Language	Result	Execution time	Memory
779501		Lobo	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3610 ms	278388 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e5+10;
const int lg = 22;

int n, q, ww, U[maxn], V[maxn], W[maxn];
vector<int> g[maxn];

int sub[maxn], block[maxn];
int tin[lg][maxn], tout[lg][maxn], timer, rtof[lg][maxn], rtlv[maxn], rtsz[maxn], nxrt[lg][maxn];

void dfssub(int u, int ant, vector<int>& verts) {
    sub[u] = 1;
    verts.pb(u);
    for(auto i : g[u]) {
        int v = u^U[i]^V[i];
        int w = W[i];
        if(block[v] || v == ant) continue;
        dfssub(v,u,verts);
        sub[u]+= sub[v];
    }
}

struct {
    vector<pair<int,int>> tr;
    vector<int> lz;

    void build(int tam) {
        tr.clear();
        lz.clear();
        tr.resize(4*(tam+5),mp(0,0));
        lz.resize(4*(tam+5),0);
    }

    void flush(int no, int l, int r) {
        tr[no].fr+= lz[no];
        if(l != r) {
            int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
            lz[lc]+= lz[no];
            lz[rc]+= lz[no];
        }
        lz[no] = 0;
    }

    void setid(int no, int l, int r, int pos, int val) {
        flush(no,l,r);
        if(l > pos || r < pos) return;
        if(l == r) {
            tr[no].sc = val;
            return;
        }

        int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
        setid(lc,l,mid,pos,val);
        setid(rc,mid+1,r,pos,val);
        tr[no] = max(tr[lc],tr[rc]);
    }

    void upd(int no, int l, int r, int ll, int rr, int val) {
        flush(no,l,r);
        if(l > rr || r < ll) return;
        if(l >= ll && r <= rr) {
            lz[no] = val;
            flush(no,l,r);
            return;
        }
        int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
        upd(lc,l,mid,ll,rr,val);
        upd(rc,mid+1,r,ll,rr,val);
        tr[no] = max(tr[lc],tr[rc]);
    }

    pair<int,int> qrymax(int no, int l, int r, int ll, int rr) {
        flush(no,l,r);
        if(l > rr || r < ll) return mp(0,0);
        if(l >= ll && r <= rr) return tr[no];
        int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
        return max(qrymax(lc,l,mid,ll,rr),qrymax(rc,mid+1,r,ll,rr));
    }

}seg[maxn];

void dfstimer(int u, int ant, int rt, int lv) {
    rtof[lv][u] = rt;
    tin[lv][u] = ++timer;

    seg[rt].setid(1,1,rtsz[rt],tin[lv][u],u);
    for(auto i : g[u]) {
        int v = u^U[i]^V[i];
        int w = W[i];
        if(block[v] || v == ant) continue;

        if(ant == -1) nxrt[lv][v] = v;
        else nxrt[lv][v] = nxrt[lv][u];

        dfstimer(v,u,rt,lv);
        seg[rt].upd(1,1,rtsz[rt],tin[lv][v],tout[lv][v],w);
    }
    tout[lv][u] = timer;
}

void buildcent(int st, int lv) {
    vector<int> verts;
    dfssub(st,-1,verts);

    int rt=-1;
    for(auto u : verts) {
        bool ok = true;

        if(sub[st]-sub[u] > sub[st]/2) ok = false;
        for(auto i : g[u]) {
            int v = u^U[i]^V[i];
            int w = W[i];
            if(block[v] || sub[u] < sub[v]) continue;
            if(sub[v] > sub[st]/2) ok = false;
        }

        if(ok) rt = u;
    }

    rtsz[rt] = sub[st];
    rtlv[rt] = lv;
    seg[rt].build(rtsz[rt]);

    timer = 0;
    dfstimer(rt,-1,rt,lv);

    block[rt] = 1;
    for(auto i : g[rt]) {
        int v = rt^U[i]^V[i];
        int w = W[i];
        if(block[v]) continue;
        buildcent(v,lv+1);
    }
}

// max_dist,vert with max_dist
pair<int,int> query(int u) {
    int lv = rtlv[u];
    pair<int,int> ans = seg[u].qrymax(1,1,rtsz[u],tin[lv][u],tout[lv][u]);
    while(lv--) {
        int rt = rtof[lv][u];

        int distme = seg[rt].qrymax(1,1,rtsz[rt],tin[lv][u],tin[lv][u]).fr;
        pair<int,int> dist = max(seg[rt].qrymax(1,1,rtsz[rt],tin[lv][rt],tin[lv][nxrt[lv][u]]-1),seg[rt].qrymax(1,1,rtsz[rt],tout[lv][nxrt[lv][u]]+1,tout[lv][rt]));
        ans = max(ans,mp(distme+dist.fr,dist.sc));
    }

    return ans;
}

void update(int u, int v, int w) {
    int lv = min(rtlv[u],rtlv[v])+1;

    while(lv--) {
        int rt = rtof[lv][u];
        if(tin[lv][u] > tin[lv][v]) swap(u,v);
        seg[rt].upd(1,1,rtsz[rt],tin[lv][v],tout[lv][v],w);
    }
}

void solve() {
    cin >> n >> q >> ww;

    for(int i = 1; i <= n-1; i++) {
        cin >> U[i] >> V[i] >> W[i];
        g[U[i]].pb(i);
        g[V[i]].pb(i);
    }

    buildcent(1,0);

    int last = 0;
    while(q--) {
        int id, neww; cin >> id >> neww;
        id = (id+last)%(n-1)+1;
        neww = (neww+last)%ww;
        int w = neww-W[id];
        W[id] = neww;

        update(U[id],V[id],w);
        // for(int i = 1; i <= n; i++) {block[i] = 0;}
        // buildcent(1,0);

        pair<int,int> d1 = query(1);
        pair<int,int> d2 = query(d1.sc);

        cout << d2.fr << endl;
        last = d2.fr;
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message (stderr)

diameter.cpp: In function 'void dfssub(long long int, long long int, std::vector<long long int>&)':
diameter.cpp:27:13: warning: unused variable 'w' [-Wunused-variable]
   27 |         int w = W[i];
      |             ^
diameter.cpp: In member function 'void<unnamed struct>::flush(long long int, long long int, long long int)':
diameter.cpp:48:35: warning: unused variable 'mid' [-Wunused-variable]
   48 |             int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
      |                                   ^~~
diameter.cpp: In function 'void buildcent(long long int, long long int)':
diameter.cpp:123:17: warning: unused variable 'w' [-Wunused-variable]
  123 |             int w = W[i];
      |                 ^
diameter.cpp:141:13: warning: unused variable 'w' [-Wunused-variable]
  141 |         int w = W[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