Submission #658697

#	Time	Username	Problem	Language	Result	Execution time	Memory
658697		mychecksedad	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	2741 ms	300528 KiB

diameter

/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD1 (1000000000+7)
#define MOD (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;



int n, q, sz[N], timer, tin[N], tout[N], num;
ll w, last = 0;
vector<int> g[N];
pair<int, ll> edges[N];
vector<bool> vis;
vector<vector<ll>> lazy, seg;
vector<array<ll, 5>> upd[N];
multiset<ll> answers, depths[N];

ll get_ans(){
    auto it = answers.end(); --it;
    return *it;
}
ll f(multiset<ll> &a){
    if(a.empty()) return 0;
    if(a.size() == 1) return *a.begin();
    auto it = a.end(); --it;
    ll x = *it; --it; x+=*it;
    return x;
}
void pre(int v, int p){
    sz[v] = 1;
    num++;
    for(int e: g[v]){
        int u = edges[e].first;
        if(u == p || vis[u]) continue;
        pre(u, v);
        sz[v] += sz[u];
    }
}

void pre2(int v, int p){
    if(g[v].size() == 1){
        tin[v] = timer;
        tout[v] = timer++;
        return;
    }
    tin[v] = MOD, tout[v] = 0;
    for(int e: g[v]){
        int u = edges[e].first;
        if(u == p || vis[u]) continue;
        pre2(u, v);
        tin[v] = min(tin[v], tin[u]);
        tout[v] = max(tout[v], tout[u]);
    }
}

int find_centroid(int v, int p){
    for(int e: g[v]){
        int u = edges[e].first;
        if(u==p || vis[u]) continue;
        if(sz[u] > num/2) return find_centroid(u, v);
    }
    return v;
}
void push(int k, int s){
    lazy[s][k<<1] += lazy[s][k];
    lazy[s][k<<1|1] += lazy[s][k];
    seg[s][k<<1] += lazy[s][k];
    seg[s][k<<1|1] += lazy[s][k];
    lazy[s][k] = 0;
}


void update(int l, int r, int ql, int qr, int k, int s, ll val, int centro){
    if(ql > r || qr < l) return;
    if(ql <= l && r <= qr){
        if(k==1){
            depths[centro].erase(depths[centro].find(seg[s][k]));
        }

        seg[s][k] += val;
        lazy[s][k] += val;

        if(k==1){
            depths[centro].insert(seg[s][k]);
        }

        return;
    }
    push(k, s);
    int m = (l+r)>>1;
    update(l, m, ql, qr, k<<1, s, val, centro);
    update(m+1, r, ql, qr, k<<1|1, s, val, centro);

    if(k==1){
        depths[centro].erase(depths[centro].find(seg[s][k]));
    }

    seg[s][k] = max(seg[s][k<<1], seg[s][k<<1|1]);

    if(k==1){
        depths[centro].insert(seg[s][k]);
    }
}

void dfs(int v, int p, int centro){
    for(int e: g[v]){
        int u = edges[e].first;
        if(u == p || vis[u]) continue;

        upd[e].pb({seg.size() - 1, tin[u], tout[u], timer, centro});
        upd[e^1].pb({seg.size() - 1, tin[u], tout[u], timer, centro});

        update(1, timer, tin[u], tout[u], 1, seg.size() - 1, edges[e].second, centro);

        dfs(u, v, centro);
    }
}

void find(int v){
    num = 0;
    pre(v, 0);
    
    if(num == 1){
        vis[v] = 1;
        return;
    }

    v = find_centroid(v, 0);

    for(int e: g[v]){
        int u = edges[e].first;
        if(vis[u]) continue;

        timer = 1;

        pre2(u, v);

        seg.pb({});
        lazy.pb({});
        seg.back().resize(4 * timer);
        lazy.back().resize(4 * timer);
        depths[v].insert(0);

        upd[e].pb({seg.size() - 1, 1, timer, timer, v});
        upd[e^1].pb({seg.size() - 1, 1, timer, timer, v});

        update(1, timer, 1, timer, 1, seg.size() - 1, edges[e].second, v);

        dfs(u, v, v);
    }
    answers.insert(f(depths[v]));
    vis[v] = 1;

    for(int e: g[v]){
        int u = edges[e].first;
        if(!vis[u]) find(u);
    }
}

void solve(){
    cin >> n >> q >> w;
    for(int i = 0; i < n - 1; ++i){
        int u, v; ll e; cin >> u >> v >> e;
        g[v].pb(i*2);
        g[u].pb(i*2+1);
        edges[2*i] = {u, e};
        edges[2*i+1] = {v, e};
    }
    vis.resize(n+1);
    find(1);
    for(;q--;){
        int d; ll e; cin >> d >> e;
        d = (d + last) % (n-1);
        e = (e + last) % w;
        ll delta = e - edges[2*d].second;
        edges[2*d].second = e;
        edges[2*d+1].second = e;
        for(auto up: upd[d*2]){
            answers.erase(answers.find(f(depths[up[4]])));
            update(1, up[3], up[1], up[2], 1, up[0], delta, up[4]);
            answers.insert(f(depths[up[4]]));
        }
        last = get_ans();
        cout << last << '\n';
    }
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
    }
    return 0;
 
}

Compilation message (stderr)

diameter.cpp: In function 'void dfs(int, int, int)':
diameter.cpp:120:31: warning: narrowing conversion of '(seg.std::vector<std::vector<long long int> >::size() - 1)' from 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
  120 |         upd[e].pb({seg.size() - 1, tin[u], tout[u], timer, centro});
      |                    ~~~~~~~~~~~^~~
diameter.cpp:121:33: warning: narrowing conversion of '(seg.std::vector<std::vector<long long int> >::size() - 1)' from 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
  121 |         upd[e^1].pb({seg.size() - 1, tin[u], tout[u], timer, centro});
      |                      ~~~~~~~~~~~^~~
diameter.cpp: In function 'void find(int)':
diameter.cpp:154:31: warning: narrowing conversion of '(seg.std::vector<std::vector<long long int> >::size() - 1)' from 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
  154 |         upd[e].pb({seg.size() - 1, 1, timer, timer, v});
      |                    ~~~~~~~~~~~^~~
diameter.cpp:155:33: warning: narrowing conversion of '(seg.std::vector<std::vector<long long int> >::size() - 1)' from 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
  155 |         upd[e^1].pb({seg.size() - 1, 1, timer, timer, v});
      |                      ~~~~~~~~~~~^~~
diameter.cpp: In function 'int main()':
diameter.cpp:204:16: warning: unused variable 'aa' [-Wunused-variable]
  204 |     int T = 1, aa;
      |                ^~

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