Submission #902524

#	Time	Username	Problem	Language	Result	Execution time	Memory
902524		fanwen	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	730 ms	49216 KiB

diameter

#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define ll long long
#define file(name)                  \
    if(fopen(name".inp", "r"))      \
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
 
 
template <class T> T max(T a, T b, T c) { return max(a, max(b, c)); }

template <class T, class U> struct lazy_segment_tree {
    int n, size, log;
    vector<T> d;
    vector<U> lazy;

    function <T(T, T)> TT;
    function <T(U, T)> UT;
    function <U(U, U)> UU;
    T T_id; U U_id;

    lazy_segment_tree(){}
    lazy_segment_tree(const vector<T>& v, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(v); }
    lazy_segment_tree(int n, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, T_id); }
    lazy_segment_tree(int n, T x, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, x); }

    void init(int n, T x) {
        this->n = n;
        log = __lg(max(n - 1, 1)) + 1, size = 1 << log;
        d = vector<T>(2 * size, T_id);
        lazy = vector<U>(size, U_id);
        for (int i = 0; i < n; i++) d[size + i] = x;
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void init(const vector <T> &v) {
        n = (int) v.size();
        log = __lg(max(n - 1, 1)) + 1, size = 1 << log;
        d = vector<T>(2 * size, T_id);
        lazy = vector<U>(size, U_id);
        for (int i = 0; i < n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void update(int k) { d[k] = TT(d[k << 1], d[k << 1 | 1]); }

    void apply(int k, U f) {
        d[k] = UT(f, d[k]);
        if (k < size) lazy[k] = UU(f, lazy[k]);
    }
    void push(int k) {
        apply(k << 1, lazy[k]);
        apply(k << 1 | 1, lazy[k]);
        lazy[k] = U_id;
    }

    void set(int p, T x) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    T get(int p) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    T get(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return T_id;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        T sml = T_id, smr = T_id;
        while (l < r) {
            if (l & 1) sml = TT(sml, d[l++]);
            if (r & 1) smr = TT(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return TT(sml, smr);
    }

    T get_all() { return d[1]; }

    void update(int p, U f) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = UT(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void update(int l, int r, U f) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) apply(l++, f);
                if (r & 1) apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(T)> int max_right(int l) {
        return max_right(l, [](T x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= n);
        assert(g(T_id));
        if (l == n) return n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        T sm = T_id;
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(TT(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(TT(sm, d[l]))) {
                        sm = TT(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = TT(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return n;
    }

    template <bool (*g)(T)> int min_left(int r) {
        return min_left(r, [](T x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= n);
        assert(g(T_id));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        T sm = T_id;
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(TT(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(TT(d[r], sm))) {
                        sm = TT(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = TT(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

    friend ostream & operator << (ostream &out, const lazy_segment_tree &seg) {
        out << "[";
        for (int i = 0; i < seg.n; ++i) {
            out << seg.get(i);
            if(i + 1 < seg.n) out << ", ";
        }
        return out << "]";
    };

};
 
const int MAX = 2e5 + 5;
 
struct edge {
    int u, v;
    long long w;
    edge(int u = 0, int v = 0, long long w = 0) : u(u), v(v), w(w) {}
    int get(int x) {
        return u ^ x ^ v;
    }
} e[MAX];
 
int n, q, m, time_in[MAX], time_out[MAX];
vector <int> adj[MAX];
long long W, last;
 
struct T {
    long long max_depth, min_depth, diam, limp, rimp;
    T(long long max_depth = 0,
         long long min_depth = 0,
         long long diam = 0,
         long long limp = 0,
         long long rimp = 0) :
        max_depth(max_depth),
        min_depth(min_depth),
        diam(diam),
        limp(limp),
        rimp(rimp) {}
};
 
T TT(const T &lhs, const T &rhs) {
    T ans;
    ans.max_depth = max(lhs.max_depth, rhs.max_depth);
    ans.min_depth = min(lhs.min_depth, rhs.min_depth);
    ans.limp = max(lhs.limp, rhs.limp, lhs.max_depth - 2 * rhs.min_depth);
    ans.rimp = max(lhs.rimp, rhs.rimp, rhs.max_depth - 2 * lhs.min_depth);
    ans.diam = max(lhs.diam, rhs.diam);
    ans.diam = max(ans.diam, lhs.max_depth + rhs.rimp, rhs.max_depth + lhs.limp);
    return ans;
}

auto UT = [] (const long long &val, const T &lhs) {
    return T(lhs.max_depth + val, lhs.min_depth + val, lhs.diam, lhs.limp - val, lhs.rimp - val);
};

auto UU = [](long long a, long long b) {
    return a + b;
}; 

lazy_segment_tree <T, long long> it;
 
void dfs(int u, int p) {
    static int run = 0;
    run++;
    for (int i : adj[u]) if(e[i].get(u) != p) {
        int v = e[i].get(u);
        time_in[i] = run;
        dfs(v, u);
        time_out[i] = run++;
        it.update(time_in[i], time_out[i], e[i].w);
    }
 
}
 
void you_make_it(void) {
    cin >> n >> q >> W;
    for (int i = 1; i < n; ++i) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        adj[e[i].u].push_back(i);
        adj[e[i].v].push_back(i);
    }

    it = lazy_segment_tree <T, long long> (2 * n, TT, UU, UT, T(), 0);
 
    dfs(1, 0);
 
    while(q--) {
        int d; long long f; cin >> d >> f;
        d = (d + last % (n - 1)) % (n - 1) + 1;
        f = (f + last) % W;
        it.update(time_in[d], time_out[d], - e[d].w);
        e[d].w = f;
        it.update(time_in[d], time_out[d], + e[d].w);
        cout << (last = it.get_all().diam) << '\n';
    }
}
 
 
signed main() {
 
#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("diameter");
    auto start_time = chrono::steady_clock::now();
 
    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
 
    you_make_it();
 
    auto end_time = chrono::steady_clock::now();
 
    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
 
    return (0 ^ 0);
}
 
// Dream it. Wish it. Do it.

Compilation message (stderr)

diameter.cpp:26:43: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   26 |     lazy_segment_tree(const vector<T>& v, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(v); }
      |                                           ^~~~
diameter.cpp:26:52: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   26 |     lazy_segment_tree(const vector<T>& v, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(v); }
      |                                                    ^~~~
diameter.cpp:26:61: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   26 |     lazy_segment_tree(const vector<T>& v, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(v); }
      |                                                             ^~~~
diameter.cpp:27:30: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   27 |     lazy_segment_tree(int n, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, T_id); }
      |                              ^~~~
diameter.cpp:27:39: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   27 |     lazy_segment_tree(int n, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, T_id); }
      |                                       ^~~~
diameter.cpp:27:48: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   27 |     lazy_segment_tree(int n, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, T_id); }
      |                                                ^~~~
diameter.cpp:28:35: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   28 |     lazy_segment_tree(int n, T x, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, x); }
      |                                   ^~~~
diameter.cpp:28:44: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   28 |     lazy_segment_tree(int n, T x, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, x); }
      |                                            ^~~~
diameter.cpp:28:53: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   28 |     lazy_segment_tree(int n, T x, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, x); }
      |                                                     ^~~~
diameter.cpp: In instantiation of 'lazy_segment_tree<T, U>::lazy_segment_tree(int, auto:26, auto:27, auto:28, T, U) [with auto:26 = T (*)(const T&, const T&); auto:27 = <lambda(long long int, long long int)>; auto:28 = <lambda(const long long int&, const T&)>; T = T; U = long long int]':
diameter.cpp:281:69:   required from here
diameter.cpp:22:24: warning: 'lazy_segment_tree<T, long long int>::UU' will be initialized after [-Wreorder]
   22 |     function <U(U, U)> UU;
      |                        ^~
diameter.cpp:21:24: warning:   'std::function<T(long long int, T)> lazy_segment_tree<T, long long int>::UT' [-Wreorder]
   21 |     function <T(U, T)> UT;
      |                        ^~
diameter.cpp:27:5: warning:   when initialized here [-Wreorder]
   27 |     lazy_segment_tree(int n, auto TT, auto UU, auto UT, T T_id, U U_id) : TT(TT), UU(UU), UT(UT), T_id(T_id), U_id(U_id) { init(n, T_id); }
      |     ^~~~~~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:303:5: note: in expansion of macro 'file'
  303 |     file("diameter");
      |     ^~~~
diameter.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:303:5: note: in expansion of macro 'file'
  303 |     file("diameter");
      |     ^~~~

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