Submission #719653

#	Time	Username	Problem	Language	Result	Execution time	Memory
719653		finn__	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3251 ms	151980 KiB

diameter

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse4")

template <typename T, size_t L>
struct SegmentTree
{
    T t[2 * L][2];

    SegmentTree()
    {
        for (size_t i = 0; i < 2 * L; i++)
        {
            t[i][0] = numeric_limits<T>::min() / 2;
            t[i][1] = 0;
        }
    }

    void build()
    {
        for (size_t i = L - 1; i; i--)
            t[i][0] = max(t[2 * i][0], t[2 * i + 1][0]);
    }

    void increment(size_t i, size_t j, T x, size_t k = 1, size_t a = 0, size_t b = L)
    {
        if (b <= i || a >= j)
            return;
        if (i <= a && b <= j)
        {
            t[k][0] += x;
            t[k][1] += x;
        }
        else
        {
            if (t[k][1])
            {
                t[2 * k][0] += t[k][1];
                t[2 * k][1] += t[k][1];
                t[2 * k + 1][0] += t[k][1];
                t[2 * k + 1][1] += t[k][1];
                t[k][1] = 0;
            }
            increment(i, j, x, 2 * k, a, (a + b) / 2);
            increment(i, j, x, 2 * k + 1, (a + b) / 2, b);
            t[k][0] = max(t[2 * k][0], t[2 * k + 1][0]);
        }
    }

    T range_max(size_t i, size_t j, size_t k = 1, size_t a = 0, size_t b = L, int64_t lbound = 0)
    {
        if (b <= i || a >= j || t[k][0] <= lbound)
            return numeric_limits<T>::min();
        if (i <= a && b <= j)
            return t[k][0];
        if (t[k][1])
        {
            t[2 * k][0] += t[k][1];
            t[2 * k][1] += t[k][1];
            t[2 * k + 1][0] += t[k][1];
            t[2 * k + 1][1] += t[k][1];
            t[k][1] = 0;
        }
        lbound = max(lbound, range_max(i, j, 2 * k, a, (a + b) / 2, lbound));
        lbound = max(lbound, range_max(i, j, 2 * k + 1, (a + b) / 2, b, lbound));
        return lbound;
    }

    void point_update(size_t i, T x)
    {
        i += L;
        t[i][0] = x;
        while (i >>= 1)
            t[i][0] = max(t[2 * i][0], t[2 * i + 1][0]);
    }
};

constexpr size_t N = 100000, K = 17;

set<pair<unsigned, unsigned>> g[N];
vector<unsigned> children[N];
unsigned subtree_size[N], subtree_range[K][N][2], edge_subtree[K][N],
    ind[K], centroid[K][N], centroid_child[K][N], level[N];
int64_t edge_weight[N];
SegmentTree<int64_t, 1 << K> t[K];
multiset<int64_t> children_height[N];
SegmentTree<int64_t, 1 << K> longest_path;

unsigned find_centroid(unsigned const u, unsigned const p, unsigned const n)
{
    subtree_size[u] = 1;
    bool all_subtrees_small = 1;
    unsigned c = UINT_MAX;

    for (auto const &[v, i] : g[u])
        if (v != p)
        {
            unsigned x = find_centroid(v, u, n);
            if (x != UINT_MAX)
                c = x;
            all_subtrees_small &= subtree_size[v] <= n / 2;
            subtree_size[u] += subtree_size[v];
        }

    if (all_subtrees_small && subtree_size[u] >= n / 2)
        c = u;
    return c;
}

void traverse(unsigned const u, unsigned const p, unsigned const d, unsigned const c, unsigned cc, int64_t const h)
{
    if (cc == UINT_MAX && p != UINT_MAX)
        cc = u;
    centroid_child[d][u] = cc;
    subtree_range[d][u][0] = ind[d]++;
    subtree_size[u] = 1;
    centroid[d][u] = c;
    t[d].t[(1 << K) + subtree_range[d][u][0]][0] = h;
    for (auto const &[v, i] : g[u])
        if (v != p)
        {
            edge_subtree[d][i] = v;
            traverse(v, u, d, c, cc, h + edge_weight[i]);
            subtree_size[u] += subtree_size[v];
        }
    subtree_range[d][u][1] = ind[d];
}

void decompose(unsigned const u, unsigned const n, unsigned const d)
{
    unsigned c = find_centroid(u, UINT_MAX, n);
    level[c] = d;
    traverse(c, UINT_MAX, d, c, UINT_MAX, 0);

    for (auto const &[v, i] : g[c])
    {
        children[c].push_back(v);
        g[v].erase(make_pair(c, i));
        decompose(v, subtree_size[v], d + 1);
    }
    g[c].clear();
}

int main()
{
    size_t n, q;
    int64_t w;
    scanf("%zu %zu %" PRId64, &n, &q, &w);

    for (size_t i = 0; i < n - 1; i++)
    {
        unsigned a, b;
        int64_t c;
        scanf("%u %u %" PRId64, &a, &b, &c);
        edge_weight[i] = c;
        g[a - 1].emplace(b - 1, i);
        g[b - 1].emplace(a - 1, i);
    }

    memset(edge_subtree, 255, sizeof edge_subtree);
    decompose(0, n, 0);
    for (size_t i = 0; i < K; i++)
        t[i].build();

    int64_t last = 0;
    for (unsigned i = 0; i < n; i++)
    {
        for (unsigned const &v : children[i])
            children_height[i].insert(
                t[level[i]].range_max(subtree_range[level[i]][v][0], subtree_range[level[i]][v][1]));
        children_height[i].insert(0);
        children_height[i].insert(0);
        longest_path.t[(1 << K) + i][0] = *children_height[i].rbegin() + *++children_height[i].rbegin();
    }

    longest_path.build();

    while (q--)
    {
        unsigned d;
        int64_t e;
        scanf("%u %" PRId64, &d, &e);
        d = (d + last) % (n - 1);
        e = (e + last) % w;

        for (size_t i = K - 2; i < K; i--)
            if (edge_subtree[i][d] != UINT_MAX)
            {
                unsigned const u = edge_subtree[i][d],
                               c = centroid[i][u],
                               cchild = centroid_child[i][u];
                children_height[c].erase(children_height[c].find(t[i].range_max(subtree_range[i][cchild][0], subtree_range[i][cchild][1])));
                t[i].increment(subtree_range[i][u][0], subtree_range[i][u][1], e - edge_weight[d]);
                children_height[c].insert(t[i].range_max(subtree_range[i][cchild][0], subtree_range[i][cchild][1]));

                longest_path.point_update(c, *children_height[c].rbegin() + *++children_height[c].rbegin());
            }

        edge_weight[d] = e;
        last = *longest_path.t[1];
        printf("%" PRId64 "\n", last);
    }
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |     scanf("%zu %zu %" PRId64, &n, &q, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:156:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         scanf("%u %u %" PRId64, &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:184:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |         scanf("%u %" PRId64, &d, &e);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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