Submission #278526

#	Time	Username	Problem	Language	Result	Execution time	Memory
278526		egekabas	Dynamic Diameter (CEOI19_diameter)	C++14	31 / 100	5079 ms	442832 KiB

diameter

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll seg[4000000];
ll lazy[4000000];
ll maxn = 1000000-1;
void push(ll v){
    seg[2*v] += lazy[v];
    seg[2*v+1] += lazy[v];
    lazy[2*v] += lazy[v];
    lazy[2*v+1] += lazy[v];
    lazy[v] = 0;
}
void upd(ll v, ll tl, ll tr, ll l, ll r, ll val){
    if(r < tl || tr < l)
        return;
    if(l <= tl && tr <= r){
        seg[v] += val;
        lazy[v] += val;
    }
    else{
        push(v);
        upd(2*v, tl, (tl+tr)/2, l, r, val);
        upd(2*v+1, (tl+tr)/2+1, tr, l, r, val);
        seg[v] = max(seg[2*v], seg[2*v+1]);
    }
}
ll get(ll v, ll tl, ll tr, ll l, ll r){
    if(r < tl || tr < l)
        return -1e18;
    if(l <= tl && tr <= r){
        return seg[v];
    }
    else{
        push(v);
        return max(
        get(2*v, tl, (tl+tr)/2, l, r),
        get(2*v+1, (tl+tr)/2+1, tr, l, r));
    }
}
struct edge{
    ll x, y, z;
};
vector<pll> g[100009];
edge e[100009];
    
ll sz[100009];
ll block[100009];
void findsz(ll v, ll prt){
    sz[v] = 1;
    for(auto u : g[v]){
        if(block[u.ff] || u.ff == prt) continue;
        findsz(u.ff, v);
        sz[v] += sz[u.ff];
    }
}
ll findcentroid(ll v, ll prt, ll totsz){
    for(auto u : g[v]){
        if(block[u.ff] || u.ff == prt) continue;
        if(sz[u.ff]*2 > totsz)
            return findcentroid(u.ff, v, totsz);
    }
    return v;
}
ll curtime = 0;
ll root;
unordered_map<ll, ll> tin[100009];
unordered_map<ll, ll> tout[100009];
vector<ll> change[100009];
vector<pll> entry[100009];
multiset<ll, greater<ll>> centmax[100009];
ll centans[100009];
multiset<ll, greater<ll>> totmax;
void dfs(ll v, ll prt){
    tin[root][v] = curtime++;
    ll distoprt;
    for(auto u : g[v]){
        if(block[u.ff])
            continue;
        if(u.ff == prt){
            change[u.ss].pb(root);
            distoprt = e[u.ss].z;
            continue;
        }
        dfs(u.ff, v);
    }
    tout[root][v] = curtime-1;
    upd(1, 0, maxn, tin[root][v], tout[root][v], distoprt);
}
void decomp(){
    findsz(root, 0);
    root = findcentroid(root, 0, sz[root]);
    tin[root][root] = -1;
    for(auto u : g[root]){
        if(block[u.ff]) continue;
        dfs(u.ff, root);
        entry[root].pb({tin[root][u.ff], tout[root][u.ff]});
        centmax[root].insert(get(1, 0, maxn, tin[root][u.ff], tout[root][u.ff]));
    }
    if(centmax[root].empty()) return;
    auto it = centmax[root].begin();
    centans[root] = *it;    
    if(centmax[root].size() >= 2){
        ++it;
        centans[root] += *it;
    }
    totmax.insert(centans[root]);
    block[root] = 1;
    ll v = root;
    for(auto u : g[v]){
        if(block[u.ff]) continue;
        root = u.ff;
        decomp();
    }
}
    
ll n, q, w;
ll last = 0;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> q >> w;
    for(ll i = 0; i < n-1; ++i){
        cin >> e[i].x >> e[i].y >> e[i].z;
        g[e[i].x].pb({e[i].y, i});
        g[e[i].y].pb({e[i].x, i});
    }
    root = 1;
    decomp();
    
    assert(curtime <= maxn);
    for(ll i = 0; i < q; ++i){
        ll d, val;
        cin >> d >> val;
        d = (d+last)%(n-1);
        val = (val+last)%w;
        ll ch = val - e[d].z;
        for(auto root : change[d]){
            ll v;
            
            if(tin[root][e[d].x] > tin[root][e[d].y])
                v = e[d].x;
            else
                v = e[d].y;
            ll in = tin[root][v];
            ll out = tout[root][v];

            pii cursub = entry[root][upper_bound(all(entry[root]), mp(in, (ll)1e18))-entry[root].begin()-1];
            centmax[root].erase(centmax[root].lower_bound(get(1, 0, maxn, cursub.ff, cursub.ss)));
            upd(1, 0, maxn, in, out, ch);
            centmax[root].insert(get(1, 0, maxn, cursub.ff, cursub.ss));
            totmax.erase(totmax.lower_bound(centans[root]));
            auto it = centmax[root].begin();
            centans[root] = *it;    
            
            if(centmax[root].size() >= 2){  
                ++it;
                centans[root] += *it;
            }
            totmax.insert(centans[root]);
        }
        last = *totmax.begin();
        cout << last << '\n';
        e[d].z = val;
    }
}

Compilation message (stderr)

diameter.cpp: In function 'void dfs(ll, ll)':
diameter.cpp:99:8: warning: 'distoprt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |     upd(1, 0, maxn, tin[root][v], tout[root][v], distoprt);
      |     ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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