제출 #1268983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268983		Bahamin	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	341 ms	65484 KiB

diameter

#include "bits/stdc++.h"

using namespace std;

template<typename A> ostream& operator<<(ostream& os, vector<A> x) {os << "{"; string sep; for (A y : x) os << sep << y, sep = ", "; return os << "}";}

#define all(a) (a).begin(), (a).end()
#define ll long long 
#define lid id << 1
#define rid id << 1 | 1
#define mid ((r + l) >> 1)
const ll MAX_N = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll LOG = 30;

ll ps[MAX_N];
vector<pair<ll, ll>> adj[MAX_N];
vector<ll> al;
ll st[MAX_N];
ll fi[MAX_N];
ll w1[MAX_N];
ll u1[MAX_N], v1[MAX_N];
ll h[MAX_N];

void dfs(ll u, ll p)
{
    st[u] = al.size();
    al.push_back(u);
    for (auto v : adj[u]) if (v.first != p) h[v.first] = h[u] + v.second, ps[v.first] = ps[u] + v.second, dfs(v.first, u), al.push_back(u);
    fi[u] = al.size();
}

struct node
{
    ll ans[3][3];
    node(){};
};

node merge(node x, node y)
{
    node re;
    for (ll i = 0; i < 3; i++) for (ll j = i; j < 3; j++) 
    {
        re.ans[i][j] = max(x.ans[i][j], y.ans[i][j]);
        for (ll p = i; p < j; p++) re.ans[i][j] = max(re.ans[i][j], x.ans[i][p] + y.ans[p + 1][j]);
    }
    return re;
}

node seg[MAX_N << 3];
ll ops[MAX_N << 3];

void build(ll l, ll r, ll id)
{
    if (l == r - 1) 
    {
        for (ll i = 0; i < 3; i++) 
        {
            ll sum = 0;
            for (ll j = i; j < 3; j++) 
            {
                if (j == 1) sum -= 2;
                else sum++;
                seg[id].ans[i][j] = 1ll * sum * ps[al[l]];
            }
        }
        return;
    }
    build(l, mid, lid);
    build(mid, r, rid);
    seg[id] = merge(seg[lid], seg[rid]);
}

void move(ll l, ll r, ll id)
{
    if (l == r - 1) return;
    for (ll i = 0; i < 3; i++)
    {
        ll sum = 0;
        for (ll j = i; j < 3; j++)
        {
            if (j == 1) sum -= 2;
            else sum++;
            seg[lid].ans[i][j] += 1ll * sum * ops[id];
            seg[rid].ans[i][j] += 1ll * sum * ops[id];
        }
    }
    ops[lid] += ops[id];
    ops[rid] += ops[id];
    ops[id] = 0;
}


void upd(ll s, ll t, ll x, ll l, ll r, ll id)
{
    move(l, r, id);
    if (s <= l && t >= r)
    {
        ops[id] += x;
        for (ll i = 0; i < 3; i++)
        {
            ll sum = 0;
            for (ll j = i; j < 3; j++)
            {
                if (j == 1) sum -= 2;
                else sum++;
                seg[id].ans[i][j] += 1ll * sum * x;
            }
        }
        return;
    }
    if (s < mid) upd(s, t, x, l, mid, lid);
    if (t > mid) upd(s, t, x, mid, r, rid);
    seg[id] = merge(seg[lid], seg[rid]);
}

void solve()
{
    ll n, q;
    cin >> n >> q;
    ll w;
    cin >> w;
    ll last = 0;
    for (ll i = 0; i < n - 1; i++)
    {
        cin >> u1[i] >> v1[i] >> w1[i];
        adj[u1[i]].push_back({v1[i], w1[i]});
        adj[v1[i]].push_back({u1[i], w1[i]});
    }
    dfs(1, 0);
    build(0, al.size(), 1);
    while (q--)
    {
        ll d; ll e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;
        if (h[u1[d]] > h[v1[d]]) swap(u1[d], v1[d]);
        upd(st[v1[d]], fi[v1[d]], e - w1[d], 0, al.size(), 1);
        w1[d] = e;
        cout << (last = seg[1].ans[0][2]) << endl;
    }
}   

int main()
{
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    ll tc = 1;
    // cin >> tc;
    while (tc--) solve();
}

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