oj.uz

Submission #940680

# Submission time Handle Problem Language Result Execution time Memory
940680 2024-03-07T13:11:56 Z Zero_OP Dynamic Diameter (CEOI19_diameter) C++14
49 / 100
 190 ms 127204 KB 
#include<bits/stdc++.h>

using namespace std;
using int64 = int64_t;

#define     REP(i, n) for(int i = 0, _n = n; i < _n; ++i)
#define    REPD(i, n) for(int i = n - 1; i >= 0; --i)
#define  FOR(i, l, r) for(int i = l, _r = r; i <= _r; ++i)
#define FORD(i, r, l) for(int i = r, _l = l; i >= _l; --i)
#define          left __left
#define         right __right
#define          prev __prev
#define          next __next
#define           div __div
#define            pb push_back
#define            pf push_front
#define         sz(v) (int)v.size()
#define      range(v) begin(v), end(v)
#define    compact(v) v.erase(unique(range(v)), end(v))
#define      debug(v) "[" #v " = " << (v) << "]"

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            a = b;
            return true;
        }
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            a = b;
            return true;
        }
        return false;
    }

template<int dimension, class T>
struct vec : public vector<vec<dimension - 1, T>> {
    static_assert(dimension > 0, "Dimension must be positive !\n");
    template<typename... Args>
    vec(int n = 0, Args... args) : vector<vec<dimension - 1, T>>(n, vec<dimension - 1, T>(args...)) {}
};

template<class T>
struct vec<1, T> : public vector<T> {
    vec(int n = 0, T val = T()) : vector<T>(n, val) {}
};

void init(void);
void process(void);

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

    #define task "antuvu"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    int T = 1; //cin >> T;
    while(T--) {
        init();
        process();
    }

    return 0;
}

const int MAX = 1e5 + 5;

int N, Q, W, timer_dfs, tin[MAX], tout[MAX], eu[MAX], ev[MAX]; int64 ew[MAX];
vector<int> adj[MAX];

struct node{
    int64 a, b, c, ab, bc, abc;
    node(){
        a = 0;
        b = 0;
        c = 0;
        ab = 0;
        bc = 0;
        abc = 0;
    }
    friend node combine(const node& L, const node& R){
        node z;
        z.a = max(L.a, R.a);
        z.b = max(L.b, R.b);
        z.c = max(L.c, R.c);
        z.ab = max({L.ab, R.ab, L.a + R.b});
        z.bc = max({L.bc, R.bc, L.b + R.c});
        z.abc = max({L.abc, R.abc, L.a + R.bc, L.ab + R.c});
        return z;
    }
};

node st[MAX * 12];
int64 lzy[MAX * 12];

void build(int id, int l, int r){
    st[id].a = 0;
    st[id].b = 0;
    st[id].c = 0;
    st[id].ab = 0;
    st[id].bc = 0;
    st[id].abc = 0;
    if(l < r){
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
}

void apply(int id, int64 delta){
    st[id].a += delta;
    st[id].b -= 2 * delta;
    st[id].c += delta;
    st[id].ab -= delta;
    st[id].bc -= delta;
    lzy[id] += delta;
}

void pushDown(int id){
    if(lzy[id] != 0){
        apply(id << 1, lzy[id]);
        apply(id << 1 | 1, lzy[id]);
        lzy[id] = 0;
    }
}

void update(int id, int l, int r, int u, int v, int64 delta){
    if(u <= l and r <= v){
        apply(id, delta);
    }
    else{
        int mid = l + r >> 1;
        pushDown(id);
        if(u <= mid) update(id << 1, l, mid, u, v, delta);
        if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, delta);
        st[id] = combine(st[id << 1], st[id << 1 | 1]);
    }
}

void preDFS(int u, int pre){
    tin[u] = tout[u] = ++timer_dfs;
    for(int id : adj[u]) if(id != pre){
        int v = eu[id] ^ ev[id] ^ u;
        preDFS(v, id);
        tout[u] = ++timer_dfs;
    }
}

void init(){
    cin >> N >> Q >> W;
    REP(i, N - 1){
        cin >> eu[i] >> ev[i] >> ew[i];
        adj[eu[i]].pb(i);
        adj[ev[i]].pb(i);
    }
}

void process(){
    preDFS(1, -1);
    build(1, 1, timer_dfs);
    REP(i, N - 1){
        if(tin[eu[i]] > tin[ev[i]]){
            swap(eu[i], ev[i]);
        }
        update(1, 1, timer_dfs, tin[ev[i]], tout[ev[i]], ew[i]);
    }

    int64 last = 0;
    while(Q--){
        int i; int64 w;
        cin >> i >> w;
        i = (last + i) % (N - 1);
        w = (last + w) % W;
        update(1, 1, timer_dfs, tin[ev[i]], tout[ev[i]], w - ew[i]);
        ew[i] = w;
        last = st[1].abc;
        cout << last << '\n';
    }
}

Compilation message

diameter.cpp: In function 'void build(int, int, int)':
diameter.cpp:111:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |         int mid = l + r >> 1;
      |                   ~~^~~
diameter.cpp: In function 'void update(int, int, int, int, int, int64)':
diameter.cpp:139:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |         int mid = l + r >> 1;
      |                   ~~^~~
diameter.cpp: In function 'int main()':
diameter.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 61784 KB Output is correct
2 Correct 12 ms 61948 KB Output is correct
3 Correct 12 ms 61868 KB Output is correct
4 Correct 12 ms 61788 KB Output is correct
5 Correct 12 ms 61788 KB Output is correct
6 Correct 13 ms 62176 KB Output is correct
7 Correct 11 ms 61788 KB Output is correct
8 Correct 12 ms 61788 KB Output is correct
9 Correct 12 ms 61788 KB Output is correct
10 Correct 12 ms 61788 KB Output is correct
11 Correct 12 ms 61992 KB Output is correct
12 Correct 12 ms 61788 KB Output is correct
13 Correct 12 ms 61788 KB Output is correct
14 Correct 12 ms 61784 KB Output is correct
15 Correct 13 ms 62008 KB Output is correct
16 Correct 12 ms 61924 KB Output is correct
17 Correct 12 ms 62044 KB Output is correct
18 Correct 13 ms 61920 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 61784 KB Output is correct
2 Correct 12 ms 61948 KB Output is correct
3 Correct 12 ms 61868 KB Output is correct
4 Correct 12 ms 61788 KB Output is correct
5 Correct 12 ms 61788 KB Output is correct
6 Correct 13 ms 62176 KB Output is correct
7 Correct 11 ms 61788 KB Output is correct
8 Correct 12 ms 61788 KB Output is correct
9 Correct 12 ms 61788 KB Output is correct
10 Correct 12 ms 61788 KB Output is correct
11 Correct 12 ms 61992 KB Output is correct
12 Correct 12 ms 61788 KB Output is correct
13 Correct 12 ms 61788 KB Output is correct
14 Correct 12 ms 61784 KB Output is correct
15 Correct 13 ms 62008 KB Output is correct
16 Correct 12 ms 61924 KB Output is correct
17 Correct 12 ms 62044 KB Output is correct
18 Correct 13 ms 61920 KB Output is correct
19 Correct 14 ms 62040 KB Output is correct
20 Correct 14 ms 62044 KB Output is correct
21 Correct 15 ms 61912 KB Output is correct
22 Correct 17 ms 62044 KB Output is correct
23 Correct 18 ms 62460 KB Output is correct
24 Correct 18 ms 62344 KB Output is correct
25 Correct 20 ms 62300 KB Output is correct
26 Correct 19 ms 62768 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 61788 KB Output is correct
2 Correct 12 ms 61788 KB Output is correct
3 Correct 12 ms 61788 KB Output is correct
4 Correct 18 ms 62068 KB Output is correct
5 Correct 40 ms 62288 KB Output is correct
6 Correct 12 ms 62048 KB Output is correct
7 Correct 12 ms 62044 KB Output is correct
8 Correct 12 ms 61852 KB Output is correct
9 Correct 13 ms 62044 KB Output is correct
10 Correct 20 ms 62044 KB Output is correct
11 Correct 50 ms 62504 KB Output is correct
12 Correct 14 ms 62300 KB Output is correct
13 Correct 14 ms 62296 KB Output is correct
14 Correct 17 ms 62300 KB Output is correct
15 Correct 22 ms 62388 KB Output is correct
16 Correct 56 ms 62804 KB Output is correct
17 Correct 57 ms 69064 KB Output is correct
18 Correct 58 ms 69064 KB Output is correct
19 Correct 58 ms 69064 KB Output is correct
20 Correct 81 ms 69228 KB Output is correct
21 Correct 143 ms 69576 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 62100 KB Output is correct
2 Correct 25 ms 62044 KB Output is correct
3 Correct 46 ms 62292 KB Output is correct
4 Correct 67 ms 62548 KB Output is correct
5 Correct 21 ms 62808 KB Output is correct
6 Correct 31 ms 62808 KB Output is correct
7 Correct 50 ms 63056 KB Output is correct
8 Correct 90 ms 63320 KB Output is correct
9 Correct 47 ms 65624 KB Output is correct
10 Correct 50 ms 65848 KB Output is correct
11 Correct 82 ms 66056 KB Output is correct
12 Correct 134 ms 66356 KB Output is correct
13 Correct 75 ms 69740 KB Output is correct
14 Correct 104 ms 69696 KB Output is correct
15 Correct 133 ms 69968 KB Output is correct
16 Correct 190 ms 70276 KB Output is correct
17 Correct 148 ms 70104 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 71 ms 127204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 61784 KB Output is correct
2 Correct 12 ms 61948 KB Output is correct
3 Correct 12 ms 61868 KB Output is correct
4 Correct 12 ms 61788 KB Output is correct
5 Correct 12 ms 61788 KB Output is correct
6 Correct 13 ms 62176 KB Output is correct
7 Correct 11 ms 61788 KB Output is correct
8 Correct 12 ms 61788 KB Output is correct
9 Correct 12 ms 61788 KB Output is correct
10 Correct 12 ms 61788 KB Output is correct
11 Correct 12 ms 61992 KB Output is correct
12 Correct 12 ms 61788 KB Output is correct
13 Correct 12 ms 61788 KB Output is correct
14 Correct 12 ms 61784 KB Output is correct
15 Correct 13 ms 62008 KB Output is correct
16 Correct 12 ms 61924 KB Output is correct
17 Correct 12 ms 62044 KB Output is correct
18 Correct 13 ms 61920 KB Output is correct
19 Correct 14 ms 62040 KB Output is correct
20 Correct 14 ms 62044 KB Output is correct
21 Correct 15 ms 61912 KB Output is correct
22 Correct 17 ms 62044 KB Output is correct
23 Correct 18 ms 62460 KB Output is correct
24 Correct 18 ms 62344 KB Output is correct
25 Correct 20 ms 62300 KB Output is correct
26 Correct 19 ms 62768 KB Output is correct
27 Correct 11 ms 61788 KB Output is correct
28 Correct 12 ms 61788 KB Output is correct
29 Correct 12 ms 61788 KB Output is correct
30 Correct 18 ms 62068 KB Output is correct
31 Correct 40 ms 62288 KB Output is correct
32 Correct 12 ms 62048 KB Output is correct
33 Correct 12 ms 62044 KB Output is correct
34 Correct 12 ms 61852 KB Output is correct
35 Correct 13 ms 62044 KB Output is correct
36 Correct 20 ms 62044 KB Output is correct
37 Correct 50 ms 62504 KB Output is correct
38 Correct 14 ms 62300 KB Output is correct
39 Correct 14 ms 62296 KB Output is correct
40 Correct 17 ms 62300 KB Output is correct
41 Correct 22 ms 62388 KB Output is correct
42 Correct 56 ms 62804 KB Output is correct
43 Correct 57 ms 69064 KB Output is correct
44 Correct 58 ms 69064 KB Output is correct
45 Correct 58 ms 69064 KB Output is correct
46 Correct 81 ms 69228 KB Output is correct
47 Correct 143 ms 69576 KB Output is correct
48 Correct 17 ms 62100 KB Output is correct
49 Correct 25 ms 62044 KB Output is correct
50 Correct 46 ms 62292 KB Output is correct
51 Correct 67 ms 62548 KB Output is correct
52 Correct 21 ms 62808 KB Output is correct
53 Correct 31 ms 62808 KB Output is correct
54 Correct 50 ms 63056 KB Output is correct
55 Correct 90 ms 63320 KB Output is correct
56 Correct 47 ms 65624 KB Output is correct
57 Correct 50 ms 65848 KB Output is correct
58 Correct 82 ms 66056 KB Output is correct
59 Correct 134 ms 66356 KB Output is correct
60 Correct 75 ms 69740 KB Output is correct
61 Correct 104 ms 69696 KB Output is correct
62 Correct 133 ms 69968 KB Output is correct
63 Correct 190 ms 70276 KB Output is correct
64 Correct 148 ms 70104 KB Output is correct
65 Runtime error 71 ms 127204 KB Execution killed with signal 11
66 Halted 0 ms 0 KB -