제출 #1262656

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

diameter

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<bool> w;
vector<ll> pa, sz, zs, ec;
vector<vector<ll> > v, ed, ch, sg, lz, wl, wr, in, de, ut, ox;
multiset<int> se;
vector<multiset<int> > sm;
int t, yu = 0;
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 j, int i, int l, int r, int x)
{
    //if (yu == 3 && j == 9)
    //    cout << "Z " << j << " " << i << " " << l << " " << r << " " << x << " " << sg[9][22] << " " << lz[9][22] << endl;
    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(j, (i << 1), l, r, x);
    upd(j, ((i << 1) ^ 1), l, r, x);
    sg[j][i] = max(sg[j][i << 1], sg[j][(i << 1) ^ 1]);
}
ll qu(int j, int i, int l, int r)
{
    //if (j == 1 && l == 2 && r == 3)
    //    cout << "Q " << i << " " << wl[j][i] << " " << wr[j][i] << endl;
    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(j, (i << 1), l, r), qu(j, ((i << 1) ^ 1), l, r));
}
void dfs(int i, int p, int u, int k, int d)
{
    //cout << "D " << i << " " << p << " " << u << " " << k << " " << d << endl;
    in[i].push_back(t);
    //cout << i << " " << in[i].size() << " " << ut[i].size() << endl;
    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);
    //cout << i << " " << in[i].size() << " " << ut[i].size() << "  " << in[i].back() << " " << ut[i].back() << " " << de[i].back() << endl;
    //if (ut[1].size() > 1)
    //    cout << "C " << ut[1][1] << endl;
}
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;
    if (p != -1)
        ch[p].push_back(u);
    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, int x)
{
    int i, j, k, tc, ts, mx, l;
    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--;
        }
        //cout << j << " " << a << " " << b << " " << ts << "   ";
        //cout << l << " " << de[ts][l] << " " << in[ts][l] << " " << ut[ts][l] << endl;
        mx = qu(j, 1, in[ts][l], ut[ts][l]);
        //cout << "U " << mx << endl;
        /*if (yu == 3 && j == 9)
        {
            for (int y = 1; y < sg[j].size(); y++)
                cout << y << " " << sg[j][y] << " " << lz[j][y] << " " << wl[j][y] << " " << wr[j][y] << endl;
        }*/
        if (sm[j].find(mx) == sm[j].end())
        {
            cout << "ASSERTION FAILED" << endl;
        }
        sm[j].erase(sm[j].find(mx));
        if (de[a][i] > de[b][k])
            upd(j, 1, in[a][i], ut[a][i], x);
        else
            upd(j, 1, in[b][k], ut[b][k], x);
        mx = qu(j, 1, in[ts][l], ut[ts][l]);
        //cout << "V " << mx << endl;
       /* if (yu == 3 && j == 9)
        {
            for (int y = 1; y < sg[j].size(); y++)
                cout << y << " " << sg[j][y] << " " << lz[j][y] << " " << wl[j][y] << " " << wr[j][y] << endl;
        }*/
        sm[j].insert(mx);
        i--;
        k--;
        se.erase(se.find(ec[j]));
        auto it = sm[j].end();
        if (it == sm[j].begin())
            ec[j] = 0;
        else
        {
            it--;
            ec[j] = (*it);
            if (it != sm[j].begin())
            {
                it--;
                ec[j] += (*it);
            }
        }
        //for (auto h : sm[j])cout << h << " ";cout << endl << ec[j] << endl;
        se.insert(ec[j]);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n, q, i, 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);
    ch.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 (i = 0; i < n; i++)
    //    cout << i << " " << pa[i] << " " << zs[i] << endl;
    for (auto g : ed)
    {
        //cout << "A " << g[0] << " " << g[1] << " " << g[2] << endl;
        ud(g[0], g[1], g[2]);
        for (auto h : ec) cout << h << " "; cout << endl;
        yu++;
        //for (auto h : ec) cout << h << " "; cout << endl;
    }
    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.end();
        it--;
        la = (*it);
        cout << la << '\n';
    }
}

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