Submission #697322

#	Time	Username	Problem	Language	Result	Execution time	Memory
697322		NintsiChkhaidze	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	4803 ms	134896 KiB

diameter

#include <bits/stdc++.h>
#define ll long long
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define pb push_back
#define pii pair<int,int>
#define s second
#define f first
using namespace std;
 
const int N = 100005,M=22; // ?
vector <pii> v[N];
vector <int> con[N];
multiset <ll> st[N],bigset;
ll value[N],wi[N];
int vis[N],xi[N],yi[N],comp[M],DP[N];
int n,centroid,CH,L;
int tin[M][N],tout[M][N],PAR[M][N],dep[M][N];
ll t[M][4*N],add[M][4*N];
multiset <ll> :: iterator it;
 
void push(int k,int h){
    if (!add[k][h]) return;
    add[k][h*2] += add[k][h];
    t[k][h*2] += add[k][h];
    add[k][h*2+1] += add[k][h];
    t[k][h*2+1] += add[k][h];
    add[k][h] = 0LL;
}
void upd(int k,int h,int l,int r,int L,int R,ll val){
    if (r < L || R < l) return;
    if (L <= l && r <= R){
        t[k][h] += val;
        add[k][h] += val;
        return;
    }
    push(k,h);
    upd(k,left,L,R,val);
    upd(k,right,L,R,val);
    t[k][h] = max(t[k][h*2],t[k][h*2+1]);
}
 
ll get(int k,int h,int l,int r,int L,int R){
    if (r < L || R < l) return 0LL;
    if (L <= l && r <= R) return t[k][h];
    push(k,h);
    return max(get(k,left,L,R),get(k,right,L,R));
}
int dfs(int x,int par,int root,int m){
    int s = 1;
    for (auto [to,idx]: v[x])
        if (to != par && !vis[to]) s += dfs(to,x,root, m);
    if (centroid == -1 && (x == root || s*2 >= m)) centroid = x;
    return s;
}
 
void DFS(int x,int par,int id,int cent){
    tin[id][x] = ++comp[id];
    PAR[id][x] = CH;
 
    for (auto [to,q]: v[x]){
        if (to == par || vis[to]) continue;
 
        con[q].pb(cent);
        dep[id][to] = dep[id][x] + 1; 
        if (dep[id][x] == 1) CH = to;
 
        DFS(to,x,id,cent);
        upd(id,1,1,n,tin[id][to],tout[id][to],+wi[q]);
    }
 
    tout[id][x] = comp[id];
}
void C(int x,int m,int lvl){
    centroid = -1;
    dfs(x, x, x, m);
    vis[centroid] = 1;
 
    L = max(L,lvl);
    DP[centroid] = lvl;
    dep[lvl][centroid] = 1;
    DFS(centroid,centroid,lvl,centroid);
 
    for (auto [to,idx]: v[centroid])
        if (!vis[to]) C(to,m/2,lvl + 1);
}
int main(){
    // ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int q; ll W;
    scanf("%d%d%lld",&n,&q,&W);
    // cin>>n>>q>>W;
 
    for (int i = 1; i < n; i++){
        cin>>xi[i]>>yi[i]>>wi[i];
        v[xi[i]].pb({yi[i],i});
        v[yi[i]].pb({xi[i],i});
    }
 
    C(1,n,1);
    for (int id = 1; id <= L; id++){
        for (int root = 1; root <= n; root++){
            if (dep[id][root] != 1) continue;
        
            for (auto [to,p]: v[root]){
                if (dep[id][to] != 2) continue;
                st[root].insert(get(id,1,1,n,tin[id][to],tout[id][to]));
            }
 
            if (st[root].size() == 1) value[root] = *st[root].begin();
            else if (st[root].size() > 1){
                it = --st[root].end(); --it;
                value[root] = *(--st[root].end()) + *it;
            }
            bigset.insert(value[root]);
        }
    }
 
    ll last=0LL;
    while (q--){
        int d; ll len;
        scanf("%d%lld",&d,&len);
        // cin>>d>>len;
        d = (d + last)%(n-1) + 1;
        len = (len + last)%W;
 
        int x = xi[d],y =yi[d]; ll delta = len - wi[d]; 
        wi[d] = len;
 
        for (int root: con[d]){
            bigset.erase(bigset.find(value[root]));
            int id = DP[root];
            if (dep[id][y] > dep[id][x]){
                int parent = PAR[id][y];
                st[root].erase(st[root].find(get(id,1,1,n,tin[id][parent],tout[id][parent])));
                upd(id,1,1,n,tin[id][y],tout[id][y],delta);
                st[root].insert(get(id,1,1,n,tin[id][parent],tout[id][parent]));
            }
            else{
                int parent = PAR[id][x]; 
                st[root].erase(st[root].find(get(id,1,1,n,tin[id][parent],tout[id][parent])));
                upd(id,1,1,n,tin[id][x],tout[id][x],delta);
                st[root].insert(get(id,1,1,n,tin[id][parent],tout[id][parent]));
            }
 
            if (st[root].size() == 1) value[root] = *st[root].begin();
            else if (st[root].size() > 1){
                it = --st[root].end(); --it;
                value[root] = *(--st[root].end()) + *it;
            }
            bigset.insert(value[root]);
        }
        last = *(--bigset.end());
        printf("%lld\n",last);
        // cout<<(last = *(--bigset.end()))<<"\n"; 
    }
    
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d%d%lld",&n,&q,&W);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
diameter.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf("%d%lld",&d,&len);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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