oj.uz

Submission #895207

# Submission time Handle Problem Language Result Execution time Memory
895207 2023-12-29T15:41:50 Z fanwen Dynamic Diameter (CEOI19_diameter) C++17
24 / 100
 203 ms 53328 KB 
#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 = 1e5 + 5;

struct edge {
    int u, v, w;
    edge(int u = 0, int v = 0, int 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

diameter.cpp: In function 'void update(int, int, int, int, int, long long int)':
diameter.cpp:78:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |     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:126:5: note: in expansion of macro 'file'
  126 |     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:126:5: note: in expansion of macro 'file'
  126 |     file("diameter");
      |     ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 5 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 5 ms 21580 KB Output is correct
7 Correct 5 ms 21084 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Correct 4 ms 21084 KB Output is correct
13 Correct 4 ms 21340 KB Output is correct
14 Correct 4 ms 21084 KB Output is correct
15 Correct 4 ms 21340 KB Output is correct
16 Correct 4 ms 21340 KB Output is correct
17 Correct 4 ms 21340 KB Output is correct
18 Correct 4 ms 21336 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 5 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 5 ms 21580 KB Output is correct
7 Correct 5 ms 21084 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Correct 4 ms 21084 KB Output is correct
13 Correct 4 ms 21340 KB Output is correct
14 Correct 4 ms 21084 KB Output is correct
15 Correct 4 ms 21340 KB Output is correct
16 Correct 4 ms 21340 KB Output is correct
17 Correct 4 ms 21340 KB Output is correct
18 Correct 4 ms 21336 KB Output is correct
19 Correct 8 ms 21336 KB Output is correct
20 Correct 8 ms 21336 KB Output is correct
21 Correct 8 ms 21468 KB Output is correct
22 Correct 10 ms 21476 KB Output is correct
23 Correct 17 ms 23640 KB Output is correct
24 Correct 12 ms 23644 KB Output is correct
25 Correct 13 ms 23900 KB Output is correct
26 Correct 15 ms 24260 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21316 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 6 ms 21344 KB Output is correct
4 Correct 12 ms 21340 KB Output is correct
5 Correct 44 ms 22356 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 5 ms 21340 KB Output is correct
8 Correct 4 ms 21284 KB Output is correct
9 Correct 5 ms 21340 KB Output is correct
10 Correct 21 ms 21824 KB Output is correct
11 Correct 82 ms 22612 KB Output is correct
12 Correct 7 ms 23644 KB Output is correct
13 Correct 9 ms 23644 KB Output is correct
14 Correct 8 ms 23644 KB Output is correct
15 Correct 23 ms 23900 KB Output is correct
16 Correct 77 ms 25172 KB Output is correct
17 Runtime error 79 ms 52972 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21336 KB Output is correct
2 Correct 16 ms 21340 KB Output is correct
3 Correct 47 ms 22088 KB Output is correct
4 Correct 83 ms 22724 KB Output is correct
5 Correct 11 ms 23784 KB Output is correct
6 Correct 20 ms 24152 KB Output is correct
7 Correct 62 ms 24764 KB Output is correct
8 Correct 120 ms 25684 KB Output is correct
9 Correct 36 ms 25680 KB Output is correct
10 Correct 48 ms 25816 KB Output is correct
11 Correct 106 ms 26504 KB Output is correct
12 Correct 203 ms 27324 KB Output is correct
13 Runtime error 69 ms 53328 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 24280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 5 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 5 ms 21580 KB Output is correct
7 Correct 5 ms 21084 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Correct 4 ms 21084 KB Output is correct
13 Correct 4 ms 21340 KB Output is correct
14 Correct 4 ms 21084 KB Output is correct
15 Correct 4 ms 21340 KB Output is correct
16 Correct 4 ms 21340 KB Output is correct
17 Correct 4 ms 21340 KB Output is correct
18 Correct 4 ms 21336 KB Output is correct
19 Correct 8 ms 21336 KB Output is correct
20 Correct 8 ms 21336 KB Output is correct
21 Correct 8 ms 21468 KB Output is correct
22 Correct 10 ms 21476 KB Output is correct
23 Correct 17 ms 23640 KB Output is correct
24 Correct 12 ms 23644 KB Output is correct
25 Correct 13 ms 23900 KB Output is correct
26 Correct 15 ms 24260 KB Output is correct
27 Correct 4 ms 21316 KB Output is correct
28 Correct 4 ms 21084 KB Output is correct
29 Correct 6 ms 21344 KB Output is correct
30 Correct 12 ms 21340 KB Output is correct
31 Correct 44 ms 22356 KB Output is correct
32 Correct 4 ms 21084 KB Output is correct
33 Correct 5 ms 21340 KB Output is correct
34 Correct 4 ms 21284 KB Output is correct
35 Correct 5 ms 21340 KB Output is correct
36 Correct 21 ms 21824 KB Output is correct
37 Correct 82 ms 22612 KB Output is correct
38 Correct 7 ms 23644 KB Output is correct
39 Correct 9 ms 23644 KB Output is correct
40 Correct 8 ms 23644 KB Output is correct
41 Correct 23 ms 23900 KB Output is correct
42 Correct 77 ms 25172 KB Output is correct
43 Runtime error 79 ms 52972 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -