제출 #1262707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262707		damjandavkov	Dynamic Diameter (CEOI19_diameter)	C++20	49 / 100	5089 ms	186232 KiB

diameter

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
using namespace std;
typedef long long ll;
vector<bool> w;
vector<int> pa, sz, zs;
vector<ll> ec;
vector<vector<int> > v, wl, wr, in, de, ut, ox;
vector<vector<ll> > ed, sg, lz;
multiset<ll> se;
vector<multiset<ll> > sm;
int t, J, L, R;
ll X;
void bl(int j, int i, int l, int r)
{
    if (sg[j].size() <= i)
    {
        sg[j].resize(i + 1);
        lz[j].resize(i + 1);
        wl[j].resize(i + 1);
        wr[j].resize(i + 1);
    }
    sg[j][i] = lz[j][i] = 0;
    wl[j][i] = l;
    wr[j][i] = r;
    if (r - l > 1)
    {
        bl(j, (i << 1), l, ((l + r) >> 1));
        bl(j, ((i << 1) ^ 1), ((l + r) >> 1), r);
    }
}
void ps(int j, int i)
{
    if ((i << 1) < sg[j].size())
    {
        sg[j][i << 1] += lz[j][i];
        lz[j][i << 1] += lz[j][i];
    }
    if (((i << 1) ^ 1) < sg[j].size())
    {
        sg[j][(i << 1) ^ 1] += lz[j][i];
        lz[j][(i << 1) ^ 1] += lz[j][i];
    }
    lz[j][i] = 0;
}
void upd(int i)
{
    ps(J, i);
    if (wl[J][i] >= R || wr[J][i] <= L)
        return;
    if (wl[J][i] >= L && wr[J][i] <= R)
    {
        sg[J][i] += X;
        lz[J][i] += X;
        ps(J, i);
        return;
    }
    upd(i << 1);
    upd((i << 1) ^ 1);
    sg[J][i] = max(sg[J][i << 1], sg[J][(i << 1) ^ 1]);
}
ll qu(int i)
{
    ps(J, i);
    if (wl[J][i] >= R || wr[J][i] <= L)
        return 0;
    if (wl[J][i] >= L && wr[J][i] <= R)
        return sg[J][i];
    return max(qu(i << 1), qu((i << 1) ^ 1));
}
void dfs(int i, int p, int u, int k, int d)
{
    in[i].push_back(t);
    de[i].push_back(d);
    if (k != -1)
        ox[i].push_back(k);
    else
        ox[i].push_back(u);
    t++;
    for (auto h : v[i])
    {
        if (h == p || w[h])
            continue;
        if (i == u)
            dfs(h, i, u, h, d + 1);
        else
            dfs(h, i, u, k, d + 1);
    }
    ut[i].push_back(t);
}
void fsz(int i, int p)
{
    sz[i] = 1;
    for (auto h : v[i])
    {
        if (h == p || w[h])
            continue;
        fsz(h, i);
        sz[i] += sz[h];
    }
}
int fcd(int i, int p, int n)
{
    for (auto h : v[i])
    {
        if (h == p || w[h])
            continue;
        if (sz[h] * 2 > n)
            return fcd(h, i, n);
    }
    return i;
}
void cd(int i, int p)
{
    fsz(i, -1);
    int n = sz[i];
    int u = fcd(i, -1, n);
    pa[u] = p;
    zs[u] = n;
    w[u] = 1;
    t = 0;
    dfs(u, -1, u, -1, 0);
    for (auto h : v[u])
    {
        if (w[h])
            continue;
        sm[u].insert(0);
        cd(h, u);
    }
}
void ud(int a, int b, ll x)
{
    int i, j, k, tc, ts, l;
    ll mx;
    i = de[a].size() - 1;
    for (j = a; j != -1; j = pa[j])
    {
        if (j == b)
            break;
        i--;
    }
    if (j == -1)
    {
        swap(a, b);
        i = de[a].size() - 1;
        for (j = a; j != -1; j = pa[j])
        {
            if (j == b)
                break;
            i--;
        }
    }
    k = de[b].size() - 1;
    for (j = b; j != -1; j = pa[j])
    {
        if (de[a][i] > de[b][k])
            ts = ox[a][i];
        else
            ts = ox[b][k];
        l = de[ts].size() - 1;
        for (tc = ts; tc != -1; tc = pa[tc])
        {
            if (tc == j)
                break;
            l--;
        }
        J = j;
        L = in[ts][l];
        R = ut[ts][l];
        mx = qu(1);
        sm[j].erase(sm[j].find(-mx));
        if (de[a][i] > de[b][k])
        {
            J = j;
            L = in[a][i];
            R = ut[a][i];
            X = x;
            upd(1);
        }
        else
        {
            J = j;
            L = in[b][k];
            R = ut[b][k];
            X = x;
            upd(1);
        }
        J = j;
        L = in[ts][l];
        R = ut[ts][l];
        mx = qu(1);
        sm[j].insert(-mx);
        i--;
        k--;
        se.erase(se.find(-ec[j]));
        auto it = sm[j].begin();
        if (it == sm[j].end())
            ec[j] = 0;
        else
        {
            ec[j] = -(*it);
            it++;
            if (it != sm[j].end())
                ec[j] -= (*it);
        }
        se.insert(-ec[j]);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q, i;
    ll a, b, c, W, la = 0;
    cin >> n >> q >> W;
    v.resize(n);
    ed.resize(n - 1);
    pa.resize(n);
    sz.resize(n);
    zs.resize(n);
    sg.resize(n);
    lz.resize(n);
    wl.resize(n);
    wr.resize(n);
    in.resize(n);
    de.resize(n);
    ut.resize(n);
    w.resize(n);
    ec.resize(n);
    sm.resize(n);
    ox.resize(n);
    for (i = 0; i < n; i++)
    {
        pa[i] = -1;
        w[i] = 0;
        ec[i] = 0;
        se.insert(0);
    }
    for (i = 0; i < n - 1; i++)
    {
        cin >> a >> b >> c;
        a--;
        b--;
        v[a].push_back(b);
        v[b].push_back(a);
        ed[i] = {a, b, c};
    }
    cd(0, -1);
    for (i = 0; i < n; i++)
        bl(i, 1, 0, zs[i]);
    for (auto g : ed)
        ud(g[0], g[1], g[2]);
    while (q--)
    {
        cin >> a >> b;
        a += la;
        a %= n - 1;
        b += la;
        b %= W;
        ud(ed[a][0], ed[a][1], b - ed[a][2]);
        ed[a][2] = b;
        auto it = se.begin();
        la = -(*it);
        cout << la << '\n';
    }
}

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