Submission #439709

#	Time	Username	Problem	Language	Result	Execution time	Memory
439709		prvocislo	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	752 ms	49832 KiB

diameter

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 1 << 17, maxv = maxn * 2;
struct node
{
    ll u, l, ul, lv, ulv, lazy; // premenne hovoria ze ktore vrcholy sme uz vybrali
    int li, ri;
    node() { u=l=ul=lv=ulv=lazy=0; }
} t[maxv * 2];
void merge(node &a, const node &l, const node &r)
{
    a.u = max(l.u, r.u), a.l = max(l.l, r.l);
    a.ul = max({l.ul, r.ul, l.u + r.l});
    a.lv = max({l.lv, r.lv, l.l + r.u});
    a.ulv = max({l.ulv, r.ulv, l.ul + r.u, l.u + r.lv});
}
void add(node &a, ll x)
{
    a.u += x, a.l -= 2 * x;
    a.ul -= x, a.lv -= x, a.lazy += x;
}
void unlazy(int vr)
{
    add(t[vr * 2 + 1], t[vr].lazy), add(t[vr * 2 + 2], t[vr].lazy);
    t[vr].lazy = 0;
}
void update(int l, int r, ll x, int vr = 0)
{
    if (l > t[vr].ri || r < t[vr].li) return;
    if (l <= t[vr].li && t[vr].ri <= r) 
        return add(t[vr], x), void();
    unlazy(vr);
    update(l, r, x, vr*2+1), update(l, r, x, vr*2+2);
    merge(t[vr], t[vr*2+1], t[vr*2+2]);
}
struct edge { int u, v; ll x; } e[maxn];
int tin[maxn], tout[maxn], p[maxn], timer = 0; ll last = 0;
vector<int> g[maxn];
void dfs(int u)
{
    tin[u] = timer++;
    for (int i : g[u])
    {
        int v = u ^ e[i].u ^ e[i].v;
        if (v == p[u]) continue;
        if (u != e[i].u) swap(e[i].u, e[i].v);
        p[v] = u; dfs(v); timer++;
    } 
    tout[u] = timer-1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = maxv - 1; i < maxv * 2; i++) t[i].li = t[i].ri = i - (maxv - 1);
    for (int i = maxv - 2; i >= 0; i--) t[i].li = t[i * 2 + 1].li, t[i].ri = t[i * 2 + 2].ri;
    int n, q; ll w;
    cin >> n >> q >> w;
    for (int i = 0; i < n - 1; i++) 
        cin >> e[i].u >> e[i].v >> e[i].x, g[--e[i].u].push_back(i), g[--e[i].v].push_back(i);
    dfs(0);
    for (int i = 0; i < n - 1; i++) 
        update(tin[e[i].v], tout[e[i].v], e[i].x);
    while (q--)
    {
        int i; ll wi; cin >> i >> wi; 
        i = ((ll)i + last) % (ll)(n-1), wi = (wi + last) % w;
        update(tin[e[i].v], tout[e[i].v], wi - e[i].x);
        e[i].x = wi;
        cout << t[0].ulv << "\n";
        last = t[0].ulv;
    }
    return 0;
}

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