Submission #711328

#	Time	Username	Problem	Language	Result	Execution time	Memory
711328		SlavicG	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	754 ms	184292 KiB

diameter

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
#define int long long
 
const int N = 8e5 + 10;
int out[N], in[N], d[N];
vector<int> a;
vector<pair<int, int>> adj[N];
 
void dfs(int u, int par) {
    in[u] = out[u] = sz(a);
    a.pb(u);
    for(auto x: adj[u]) {
        int v = x.first, w = x.second;
        if(v == par) continue;
        d[v] = d[u] + w;
        dfs(v, u);
        out[u] = sz(a);
        a.pb(u);
    }
}
 
struct node {
    int prefix, sufix, ans, max_depth, max_lca;
};
 
node merge(node a, node b) {
    node c;
    c.prefix = max({a.prefix, b.prefix, b.max_depth + a.max_lca});
    c.sufix = max({a.sufix, b.sufix, a.max_depth + b.max_lca});
    c.max_depth = max(a.max_depth, b.max_depth);
    c.max_lca = max(a.max_lca, b.max_lca);
    c.ans = max({a.ans, b.ans, a.sufix + b.max_depth, a.max_depth + b.prefix});
    return c;
}
 
node t[4 * N];
int lazy[4 * N];
 
void push(int i, int l, int r) {
    if(!lazy[i]) return;
    t[i].max_depth += lazy[i];
    t[i].max_lca -= 2 * lazy[i];
    t[i].prefix -= lazy[i];
    t[i].sufix -= lazy[i];
    if(l != r) {
        lazy[2 * i] += lazy[i];
        lazy[2 * i + 1] += lazy[i];
    }
    lazy[i] = 0;
}
void modif(int i, int l, int r, int tl, int tr, int val) {
    push(i, l, r);
    if(l > tr || r < tl) return;
    if(l >= tl && r <= tr) {
        lazy[i] += val;
        push(i, l, r);
        return;
    }
    push(i, l, r);
    int mid = l + r >> 1;
    modif(2 * i, l, mid, tl, tr, val);
    modif(2 * i + 1, mid + 1, r, tl, tr, val);
    t[i] = merge(t[2 * i], t[2 * i + 1]);
}
const int inf = 1e18;
const node neutral = {-inf, -inf, -inf, -inf, -inf};
 
void build(int i, int l, int r) {
    if(l > r) return;
    if(l == r) {
        t[i].max_depth = d[a[l]];
        t[i].max_lca = -2 * d[a[l]];
        t[i].prefix = -inf;
        t[i].sufix = -inf;
        t[i].ans = -inf;
        return;
    }
    int mid = l + r >> 1;
    build(2 * i, l, mid);
    build(2 * i + 1, mid + 1, r);
    t[i] = merge(t[2 * i], t[2 * i + 1]);
}
void solve() {
    a.clear();
    for(int i = 0; i < 4 * N; ++i) t[i] = neutral;
    int n, q, w; cin >> n >> q >> w;
    vector<pair<int, int>> edges;
    map<pair<int, int>, int> mp;
    for(int i = 0; i < n - 1; ++i) {
        int u, v, c; cin >> u >> v >> c; --u, --v;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
        edges.pb({u, v});
        mp[{u, v}] = mp[{v, u}] = c;
    }
    dfs(0, -1);
    for(int i = 0; i < n - 1; ++i) {
        if(in[edges[i].first] > in[edges[i].second]) swap(edges[i].first, edges[i].second);
    }
    build(1, 0, sz(a) - 1);
    int last = 0;
    while(q--) {
        int d, e; cin >> d >> e; d = (d + last) % (n - 1), e = (e + last) % w;
        modif(1, 0, sz(a) - 1, in[edges[d].second], out[edges[d].second], e - mp[{edges[d].first, edges[d].second}]);
        last = max(t[1].ans, t[1].max_depth);
        mp[{edges[d].first, edges[d].second}] = mp[{edges[d].second, edges[d].first}] = e;
        cout << last << "\n";
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

Compilation message (stderr)

diameter.cpp: In function 'void modif(long long int, long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:70:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int mid = l + r >> 1;
      |               ~~^~~
diameter.cpp: In function 'void build(long long int, long long int, long long int)':
diameter.cpp:88:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |     int mid = l + r >> 1;
      |               ~~^~~

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