Submission #940683

#	Time	Username	Problem	Language	Result	Execution time	Memory
940683		Zero_OP	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	324 ms	63924 KiB

diameter

#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, timer_dfs, tin[MAX], tout[MAX], eu[MAX], ev[MAX]; int64 W, 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 * 2 * 4];
int64 lzy[MAX * 2 * 4];

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 (stderr)

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 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27