Submission #266970

#	Time	Username	Problem	Language	Result	Execution time	Memory
266970		johutha	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5049 ms	225960 KiB

diameter

#include <iostream>
#include <vector>
#include <set>

#define int long long
#define log2(x) (sizeof(long long)*8 - __builtin_clzll(x))

using namespace std;

struct segtree
{
    vector<int> table;
    vector<int> ops;

    void apply(int pos, int val)
    {
        ops[pos] += val;
        table[pos] += val;
    }

    void propagate(int pos)
    {
        apply(2*pos + 1, ops[pos]);
        apply(2*pos + 2, ops[pos]);
        ops[pos] = 0;
    }

    int query(int ql, int qr, int l, int r, int pos)
    {
        if (ql <= l && r <= qr) return table[pos];
        if (r < ql || qr < l) return -1;
        propagate(pos);
        return max(query(ql, qr, l, (l + r)/2, 2*pos + 1), query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2));
    }

    void update(int ql, int qr, int val, int l, int r, int pos)
    {
        if (ql <= l && r <= qr)
        {
            apply(pos, val);
            return;
        }
        if (r < ql || qr < l) return;
        propagate(pos);
        update(ql, qr, val, l, (l + r)/2, 2*pos + 1);
        update(ql, qr, val, (l + r)/2 + 1, r, 2*pos + 2);

        table[pos] = max(table[2*pos + 1], table[2*pos + 2]);
    }

    void build(const vector<int>& vs, int l, int r, int pos)
    {
        if (l == r)
        {
            table[pos] = vs[l];
            return;
        }
        build(vs, l, (l + r)/2, 2*pos + 1);
        build(vs, (l + r)/2 + 1, r, 2*pos + 2);
        table[pos] = max(table[2*pos + 1], table[2*pos + 2]);
    }
};

struct tree
{
    int n;
    int logn;
    vector<vector<pair<int,int>>> adjlist;
    vector<vector<int>> prein;
    vector<vector<int>> preout;
    vector<vector<int>> root;
    vector<vector<int>> desc;
    vector<vector<int>> depth;
    vector<int> sz;
    vector<multiset<int, greater<int>>> tvals;
    vector<segtree> trees;
    multiset<int, greater<int>> mvals;
    vector<int> lvl;
    vector<pair<int,int>> edges;
    vector<int> weights;

    int getmx(int ms)
    {
        return (*tvals[ms].begin()) + (*next(tvals[ms].begin()));
    }

    int update(int ind, int val)
    {
        auto vp = edges[ind];
        int mlv = min(lvl[vp.first], lvl[vp.second]);
        int nd = val - weights[ind];
        weights[ind] = val;

        for (int i = 0; i <= mlv; i++)
        {
            int v = (depth[vp.first][i] < depth[vp.second][i] ? vp.second : vp.first);
            int rt = root[v][i];

            mvals.erase(mvals.find(getmx(rt)));
            int dsc = desc[v][i];

            int sv = trees[rt].query(prein[dsc][i], preout[dsc][i], 0, sz[rt] - 1, 0);
            tvals[rt].erase(tvals[rt].find(sv));
            trees[rt].update(prein[v][i], preout[v][i], nd, 0, sz[rt] - 1, 0);

            sv = trees[rt].query(prein[dsc][i], preout[dsc][i], 0, sz[rt] - 1, 0);
            tvals[rt].insert(sv);

            mvals.insert(getmx(rt));
        }

        return *mvals.begin();
    }

    void prefdfs(int curr, int par, int lv, int& ord, int dsc, int dpth, vector<int>& dsts, int dist, int rt)
    {
        if (lvl[curr] < lv) return;
        root[curr][lv] = rt;
        prein[curr][lv] = ord;
        desc[curr][lv] = dsc;
        depth[curr][lv] = dpth;
        dsts.push_back(dist);
        ord++;
        
        for (auto np : adjlist[curr])
        {
            int next = np.first;
            if (next == par) continue;
            prefdfs(next, curr, lv, ord, (dsc == -1 ? next : dsc), dpth + 1, dsts, dist + np.second, rt);
        }
        preout[curr][lv] = ord - 1;
    }

    void precalcdia()
    {
        logn = log2(n);
        prein.resize(n, vector<int>(logn, -1));
        preout.resize(n, vector<int>(logn, -1));
        root.resize(n, vector<int>(logn, -1));
        desc.resize(n, vector<int>(logn, -1));
        depth.resize(n, vector<int>(logn, -1));
        sz.resize(n, -1);
        tvals.resize(n);
        trees.resize(n);
        lvl.resize(n, -1);

        for (int i = 0; i < n; i++)
        {
            vector<int> ds;
            int ord = 0;
            int lv = lvl[i];
            prefdfs(i, -1, lv, ord, -1, 0, ds, 0, i);
            trees[i].table.resize(4*ord, -1);
            trees[i].ops.resize(4*ord, 0);
            trees[i].build(ds, 0, ord - 1, 0);
            tvals[i].insert(0);
            tvals[i].insert(0);
            sz[i] = ord;

            for (auto np : adjlist[i])
            {
                int next = np.first;
                if (lvl[next] < lv) continue;
                int sv = trees[i].query(prein[next][lv], preout[next][lv], 0, ord - 1, 0);
                tvals[i].insert(sv);
            }
            mvals.insert(getmx(i));
        }
    }

    vector<int> ssz;

    int szdfs(int curr, int par)
    {
        if (lvl[curr] != -1) return 0;
        ssz[curr] = 1;

        for (auto np : adjlist[curr])
        {
            int next = np.first;
            if (next == par) continue;
            ssz[curr] += szdfs(next, curr);
        }

        return ssz[curr];
    }

    int cntdfs(int curr, int par, int sbz)
    {
        for (auto np : adjlist[curr])
        {
            int next = np.first;
            if (next == par || lvl[next] != -1) continue;
            if (ssz[next] > sbz / 2) return cntdfs(next, curr, sbz);
        }
        return curr;
    }

    void findcentroid(int nrt, int lv)
    {
        szdfs(nrt, -1);
        int cent = cntdfs(nrt, -1, ssz[nrt]);
        lvl[cent] = lv;

        for (auto np : adjlist[cent])
        {
            int next = np.first;
            if (lvl[next] == -1) findcentroid(next, lv + 1);
        }
    }

    void precalc()
    {
        lvl.resize(n, - 1);
        ssz.resize(n, -1);
        findcentroid(0, 0);
        precalcdia();
        // print();
    }
};

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, q, m;
    cin >> n >> q >> m;

    tree t;
    t.n = n;
    t.adjlist.resize(n);
    t.edges.resize(n - 1);
    t.weights.resize(n - 1);

    for (int i = 0; i < n - 1; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        a--; b--;
        t.edges[i] = make_pair(a, b);
        t.weights[i] = w;
        t.adjlist[a].emplace_back(b, w);
        t.adjlist[b].emplace_back(a, w);
    }

    t.precalc();
    int last = 0;

    for (int i = 0; i < q; i++)
    {
        int d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % m;
        last = t.update(d, e);
        cout << last << "\n";
    }
}

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