Submission #895209

#	Time	Username	Problem	Language	Result	Execution time	Memory
895209		fanwen	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	374 ms	64080 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)); }

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 info {
    long long max_depth, min_depth, diam, limp, rimp;
    info(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) {}
};

info operator + (const info &lhs, const info &rhs) {
    info 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;
}

info it[4 * MAX];
long long lazy[4 * MAX];

void apply(int idx, long long val) {
    info &p = it[idx];
    p.max_depth += val;
    p.min_depth += val;
    p.limp -= val;
    p.rimp -= val;
    lazy[idx] += val;
}

void push(int p) {
    if(lazy[p] == 0) return;
    apply(p << 1, lazy[p]);
    apply(p << 1 | 1, lazy[p]);
    lazy[p] = 0;
}

void update(int idx, int l, int r, int u, int v, long long val) {
    if(l > v || r < u) return;
    if(l >= u && r <= v) return apply(idx, val);

    push(idx);
    int mid = l + r >> 1;
    update(idx << 1, l, mid, u, v, val);
    update(idx << 1 | 1, mid + 1, r, u, v, val);

    it[idx] = it[idx << 1] + it[idx << 1 | 1];
}

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++;
        update(1, 1, 2 * n, time_in[i] + 1, 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);
    }

    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;
        update(1, 1, 2 * n, time_in[d] + 1, time_out[d], - e[d].w);
        e[d].w = f;
        update(1, 1, 2 * n, time_in[d] + 1, time_out[d], + e[d].w);
        cout << (last = it[1].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: In function 'void update(int, int, int, int, int, long long int)':
diameter.cpp:79:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     int mid = l + r >> 1;
      |               ~~^~~
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:127:5: note: in expansion of macro 'file'
  127 |     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:127:5: note: in expansion of macro 'file'
  127 |     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