Submission #198111

#	Time	Username	Problem	Language	Result	Execution time	Memory
198111		model_code	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	5028 ms	162020 KiB

diameter

#include <vector>
#include <stack>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <iomanip>
#include <set>
#include <functional>
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;

#define x first
#define y second
typedef std::pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<ui, ui> puu;

template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;

ui logceil(ll x) { return x ? 8 * sizeof(ll) - __builtin_clzll(x) : 0; }

namespace std {
template<typename T, typename U>struct hash<pair<T, U>> {
        hash<T>t;
        hash<U>u;
        size_t operator()(const pair<T, U>&p)const {
                return t(p.x) ^ (u(p.y) << 7);
        }
};
}


template <typename EdgeType>
class DFSOrder {
public:
        DFSOrder(const vector<vector<EdgeType>> &_E) : T(0), N(_E.size()), E(_E), RevEnter(N), Enter(N), Exit(N) {
                dfs(0, -1);
        }

        vector<vector<EdgeType>> linearize() {
                vector<vector<EdgeType>> F(N);
                for (int i = 0; i < N; ++i) {
                        for (auto v : E[i]) {
                                F[conv(i)].push_back(conv(v));
                        }
                }
                return F;
        }

        void dfs(int u, int p) {
                RevEnter[T] = u;
                Enter[u] = T++;
                for (auto v : E[u]) if (t(v) != p) dfs(t(v), u);
                Exit[u] = T;
        }

        inline int t(const int&e) const {
                return e;
        }
        template <typename U> inline int t(const pair<int, U>&e) const {
                return e.x;
        }

        inline int conv(const int&e) const {
                return Enter[e];
        }
        template <typename U> inline pair<int, U> conv(const pair<int, U>&e) const {
                return {Enter[e.x], e.y};
        }

        const vector<int> &revEnter() const {
                return RevEnter;
        }
        const vector<int> &enter() const {
                return Enter;
        }
        const vector<int> &exit() const {
                return Exit;
        }

        int T, N;
        const vector<vector<EdgeType>> &E;
        vector<int> Enter, Exit, RevEnter;
};

/** Centroid decomposition.
 *
 * Input: graph as adjacency list (either int or pair<int,T>)
 * Output: array U of integers of size |V|
 *
 * Here, U[v] is the bfs order in the centroid tree. For DFS, only process
 * vertices with higher U[w] when processing centroid v, for instance:
 *
 * void dfs(int u, int p, int ctr, ...) {
 *      ....
 *      for (int v:E[u]) {
 *          if (v != p && U[v] > U[ctr]) {
 *              dfs(v, u, ctr, ...);
 *          }
 *      }
 * }
 */
template <typename EdgeType>
class CentroidDecomposition {
public:
        CentroidDecomposition(const vector<vector<EdgeType>> &E) : E(E) {}

        const vector<int>& findCentroids() {
                DFSOrder<EdgeType> DFS(E);
                auto EF = DFS.linearize();
                
                N = E.size();
                U.assign(N, -1);

                for (int j = 0; j < N; ) {
                        for (int i = N - 1; i >= 0; --i) {
                                if (U[i] >= 0) continue;

                                U[i] = -1;
                                bool root = true;
                                for (auto v : EF[i]) {
                                        if (U[t(v)] < 0) {
                                                if (t(v) > i) U[i] += U[t(v)];
                                                else root = false;
                                        }
                                }

                                if (root) {
                                        int n = -U[i], u = i, p = -1;
                                        while (true) {
                                                int s = n + U[u];
                                                for (auto v : EF[u]) if (t(v) != p && U[t(v)] < 0) s = max(s, -U[t(v)]);
                                                if (2 * s <= n) {
                                                        U[u] = j++;
                                                        break;
                                                } else {
                                                        for (auto v : EF[u]) if (t(v) != p && -U[t(v)] > n / 2) {
                                                                        p = u;
                                                                        u = t(v);
                                                                        break;
                                                                }
                                                }
                                        }
                                }
                        }
                }
                vector<int> Ans(N);
                for (int i = 0; i < N; ++i) Ans[i] = U[DFS.enter()[i]];
                swap(Ans, U);
                return U;
        }

        inline int t(const int&e) const {
                return e;
        }
        template <typename U> inline int t(const pair<int, U>&e) const {
                return e.x;
        }

        int N;
        const vector<vector<EdgeType>> &E;
        vector<int> U;
};

template<typename F>struct NoOp {
        void setup(ui, F) {} void op(F&p, F n, ui, ui) {
                p = n;
        } void down(F&, F&, F&, ui, ui) {}
};

template<typename F, typename SetOp, typename PowerOp>struct Lazy {
        void setup(ui s, F def) {
                this->def = def;
                this->s = s;
                L = new F[s]();
                fill(L, L + s, def);
        }
        void down(F&u, F&l, F&r, ui i, ui s) {
                op(l, L[i], i << 1, s>>1);
                op(r, L[i], i << 1 | 1, s >> 1);
                L[i] = def;
        }
        void op(F&p, F n, ui i, ui s) {
                p = sop(p, pop(n, s));
                if(i < this->s)this->L[i] = sop(this->L[i], n);
        }
        SetOp sop;
        PowerOp pop;
        F*L;
        ui s;
        F def;
};

template <typename F, typename CombineOp, typename ModifyOp = NoOp<F>> struct SegTree {
        void setup(ui s, F def) {
                n = 1 << logceil(s);
                T = vector<F>(2 * n, def);
                for (ui i = n - 1; i > 0; i--) T[i] = cop(T[i << 1], T[i << 1 | 1]);
                mop.setup(2 * n, def);
        }

        void setup(vector<F> & data, F def = F(), F def2 = F()) {
                n = 1 << logceil(data.size());
                T = vector<F>(2 * n, def);
                copy(data.begin(), data.end(), T.begin() + n);
                for (ui i = n - 1; i > 0; i--) T[i] = cop(T[i << 1], T[i << 1 | 1]);
                mop.setup(2 * n, def2);
        }

        inline void put(ui x, F n) {
                put(x, x, n);
        }
        inline void put(ui from, ui to, F v) {
                put2(from, to + 1, v, 1, n);
        }
        inline F get(ui x) {
                return get(x, x);
        }
        inline F get(ui from, ui to) {
                return get2(from, to + 1, 1, n);
        }

        void put2(ui from, ui to, F v, ui i, ui s) {
                if (from == 0 && to == s) {
                        mop.op(T[i], v, i, s);
                        return;
                }
                mop.down(T[i], T[i << 1], T[i << 1 | 1], i, s);
                s >>= 1;
                i <<= 1;
                if (to <= s) {
                        put2(from, to, v, i, s);
                } else if (from >= s) {
                        put2(from - s, to - s, v, i | 1, s);
                } else {
                        put2(from, s, v, i, s);
                        put2(0, to - s, v, i | 1, s);
                }
                T[i >> 1] = cop(T[i], T[i | 1]);
        }

        F get2(ui from, ui to, ui i, ui s) {
                while (true) {
                        if (from == 0 && to == s) return T[i];
                        mop.down(T[i], T[i << 1], T[i << 1 | 1], i, s);
                        s >>= 1;
                        i <<= 1;
                        if (to > s) {
                                to -= s;
                                if (from >= s) {
                                        from -= s;
                                        i |= 1;
                                } else return cop(get2(from, s, i, s), get2(0, to, i | 1, s));
                        }
                }
        }

        ui n;
        vector<F> T;
        CombineOp cop;
        ModifyOp mop;
};


template <typename F> struct AddOp {
        F operator()(F a, F b) {
                return a + b;
        }
};
template <typename F> struct MinOp {
        F operator()(F a, F b) {
                return std::min(a, b);
        }
};
template <typename F> struct MaxOp {
        F operator()(F a, F b) {
                return std::max(a, b);
        }
};
template <typename F> struct MultiplyOp {
        F operator()(F a, F b) {
                return a * b;
        }
};
template <typename F> struct MultOp {
        F operator()(F a, ui b) {
                return a * b;
        }
};
template <typename F> struct IdempOp {
        F operator()(F a, ui b) {
                return a;
        }
};
template <typename F> struct InverseOp {
        F operator()(F a, F b) {
                return b ? b - a : a;
        }
};

template<typename T> using AddSumTree = SegTree<T, AddOp<T>, Lazy<T, AddOp<T>, MultOp<T>>>;
template<typename T> using AddMaxTree = SegTree<T, MaxOp<T>, Lazy<T, AddOp<T>, IdempOp<T>>>;
template<typename T> using AddMinTree = SegTree<T, MinOp<T>, Lazy<T, AddOp<T>, IdempOp<T>>>;
template<typename T> using AssignMinTree = SegTree<T, MinOp<T>, Lazy<T, MinOp<T>, IdempOp<T>>>;
template<typename T> using AssignMaxTree = SegTree<T, MaxOp<T>, Lazy<T, MaxOp<T>, IdempOp<T>>>;
template<typename T> using XorTree = SegTree<T, AddOp<T>, Lazy<T, InverseOp<T>, MultOp<T>>>;

template<typename T> using SetMinTree = SegTree<T, MinOp<T>>;
template<typename T> using SetMaxTree = SegTree<T, MaxOp<T>>;
template<typename T> using SetMulTree = SegTree<T, MultiplyOp<T>>;


class Diameter {
public:
        // all edges (target, initial_cost)
        vector<vector<pair<int, ll>>> E;

        // level on which vertex is a centroid
        vector<int> Level;

        // (u,v) -> (centroid, root_edge_id),(left,right)
        // left-right is range of leaves (by dfs visit time) that hang below this edge
        // size of each vector is <= log N (by centroid decomposition)
        unordered_map<pii, vector<pair<pii, pii>>> EdgeToCtr;

        // for each centroid, the sum of root to leaf path, leaves ordered by dfs visit times
        // only used in the setup phase, then superseded by LeafDepths
        vector<vector<ll>> RootToLeafPath;

        // for each centroid the prefix sums of the subtrees hanging under edges adjacent to centroid
        vector<vector<int>> CentroidChildSubtreeSizes;

        // range add and range max; initialised by LeafDepths
        vector<AddMaxTree<ll>> LeafDepths;

        // per centroid, maximum root-to-leaf path for each edge adjacent to centroid
        vector<multiset<ll>> CtrMax;

        // per centroid, maximum cost path in that centroid
        multiset<ll> AllMax;

        void dfs(int u, int p, int ctr, int j, ll cost, int &T) {
                bool isLeaf = true;
                for (auto v : E[u]) {
                        if (v.x != p && Level[v.x] > Level[ctr]) {
                                isLeaf = false;
                                int begin = T;
                                dfs(v.x, u, ctr, j, cost + v.y, T);
                                int end = T;
                                EdgeToCtr[ {u, v.x}].push_back({{ctr, j}, {begin, end - 1}});
                                EdgeToCtr[ {v.x, u}].push_back({{ctr, j}, {begin, end - 1}});
                        }
                }

                if (isLeaf) {
                        RootToLeafPath[ctr].push_back(cost);
                        T++;
                }
        }

        void buildForCentroid(int u) {
                CentroidChildSubtreeSizes[u].push_back(0);
                int root_edges = 0, T = 0;
                for (auto v : E[u]) {
                        if (Level[v.x] > Level[u]) {
                                int begin = T;
                                dfs(v.x, u, u, ++root_edges, v.y, T);
                                int end = T;
                                EdgeToCtr[ {u, v.x}].push_back({{u, root_edges}, {begin, end - 1}});
                                EdgeToCtr[ {v.x, u}].push_back({{u, root_edges}, {begin, end - 1}});
                                CentroidChildSubtreeSizes[u].push_back(T);
                        }
                }

                if (root_edges > 0) {
                        LeafDepths[u].setup(RootToLeafPath[u], 0LL);
                        for (int i = 1; i <= root_edges; ++i) {
                                CtrMax[u].insert(maxForRootEdge(u, i));
                        }
                        AllMax.insert(maxForCentroid(u));
                }
        }

        ll maxForRootEdge(int u, int i) {
                return LeafDepths[u].get(CentroidChildSubtreeSizes[u][i - 1], CentroidChildSubtreeSizes[u][i] - 1);
        }

        ll maxForCentroid(int u) {
                if (CtrMax[u].empty()) {
                        return 0LL;
                } else if (CtrMax[u].size() == 1) {
                        return *CtrMax[u].rbegin();
                } else {
                        return *CtrMax[u].rbegin() + *next(CtrMax[u].rbegin());
                }
        }

        void remove(multiset<ll>&M, ll x) {
                M.erase(M.find(x));
        }

        void solve(istream& cin, ostream& cout) {
                int N, Q; ll W;
                cin >> N >> Q >> W;
                vector<pair<int, int> > _edges;
                vector<ll> _edge_w;

                E.resize(N);
                _edges.resize(N);
                _edge_w.resize(N);

                RootToLeafPath.resize(N);
                CentroidChildSubtreeSizes.resize(N);
                LeafDepths.resize(N);
                CtrMax.resize(N);
                for (int i = 0; i < N - 1; ++i) {
                        int a, b;
                        ll c;
                        
                        cin >> a >> b >> c;
                        --a;
                        --b;
                        _edges[i] = {a, b};
                        _edge_w[i] = c;
                        E[a].emplace_back(b, c);
                        E[b].emplace_back(a, c);
                }


                CentroidDecomposition<pair<int, ll>> C{E};
                Level = C.findCentroids();
                for (int i = 0; i < N; ++i) {
                        buildForCentroid(i);
                }

                ll last = 0; //*AllMax.rbegin();
                int cnt = 0;
                for (int q = 0; q < Q; ++q) {
                        int i;
                        ll c;
                        cin >> i >> c;
                        i = (i + last) % (N - 1);
                        c = (c + last) % W;
                        auto [a, b] = _edges[i];
                        ll rel_c = c - _edge_w[i];
                        _edge_w[i] = c;

                        // process (a,b) in all centroids in which this edge exists
                        for (auto e : EdgeToCtr[ {a, b}]) {
                                int ctr = e.x.x;
                                int i = e.x.y;
                                int l = e.y.x;
                                int r = e.y.y;

                                remove(AllMax, maxForCentroid(ctr));
                                remove(CtrMax[ctr], maxForRootEdge(ctr, i));

                                LeafDepths[ctr].put(l, r, rel_c);

                                CtrMax[ctr].insert(maxForRootEdge(ctr, i));
                                AllMax.insert(maxForCentroid(ctr));
                        }

                        ll cur = *AllMax.rbegin();
                        cout << cur << '\n';
                        //cnt += last != cur;
                        last = cur;
                }
                //cerr << cnt << '\n';
        }
};


int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        Diameter solver;
        std::istream& in(std::cin);
        std::ostream& out(std::cout);
        solver.solve(in, out);
        return 0;
}

Compilation message (stderr)

diameter.cpp: In member function 'void Diameter::solve(std::istream&, std::ostream&)':
diameter.cpp:443:21: warning: unused variable 'cnt' [-Wunused-variable]
                 int cnt = 0;
                     ^~~
diameter.cpp: In instantiation of 'DFSOrder<EdgeType>::DFSOrder(const std::vector<std::vector<_Tp> >&) [with EdgeType = std::pair<int, long long int>]':
diameter.cpp:115:36:   required from 'const std::vector<int>& CentroidDecomposition<EdgeType>::findCentroids() [with EdgeType = std::pair<int, long long int>]'
diameter.cpp:437:41:   required from here
diameter.cpp:89:34: warning: 'DFSOrder<std::pair<int, long long int> >::RevEnter' will be initialized after [-Wreorder]
         vector<int> Enter, Exit, RevEnter;
                                  ^~~~~~~~
diameter.cpp:89:21: warning:   'std::vector<int> DFSOrder<std::pair<int, long long int> >::Enter' [-Wreorder]
         vector<int> Enter, Exit, RevEnter;
                     ^~~~~
diameter.cpp:42:9: warning:   when initialized here [-Wreorder]
         DFSOrder(const vector<vector<EdgeType>> &_E) : T(0), N(_E.size()), E(_E), RevEnter(N), Enter(N), Exit(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