Submission #1098912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098912		RiverFlow	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	755 ms	47400 KiB

diameter

#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

void prepare(); void main_code();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}

void prepare() {};


int n, q;
long long w;

struct edge {
    int u, v;
    long long w;
    edge () {};
    edge (int _u, int _v, long long _w) {
        u = _u, v = _v, w = _w;
    }
    int get(int x) {
        return x ^ u ^ v;
    }
    bool operator < (const edge & other) {
        return w < other.w;
    }
} e[N];

vector<int> g[N];

int par[N];

long long d[N];
int s[N], tin[N], tout[N], cnt = 0;
void euler(int u, int p) {
    s[u] = 1;
    tin[u] = ++cnt;
    for(int id : g[u]) {
        int v = e[id].get(u);
        if (v != p) {
            par[v] = u;
            d[v] = d[u] + e[id].w;
            euler(v, u);
            s[u] += s[v];
        }
    }
    tout[u] = ++cnt;
}
int cc = 0, ch[N], hd[N], pos[N], nxt[N], base[N];
void hld(int u, int p) {
    pos[u] = ++cnt;
    base[cnt] = u;
    ch[u] = cc;
    if (hd[cc] == 0) hd[cc] = u;
    int mx = -1;
    for(int id : g[u]) {
        int v = e[id].get(u);
        if (v != p) {
            if (mx == -1 or s[v] > s[mx])
                mx = v;
        }
    }
    if (mx == -1) return ;
    nxt[u] = mx;
    hld(mx, u);
//    cerr << u << ' ' << mx << nl;
    for(int id : g[u]) {
        int v = e[id].get(u);
        if (v != p and v != mx) {
            ++cc;
            hld(v, u);
        }
    }
}


namespace IT {
    int arr[2 * N];
    struct segment_tree {
        int n;
        vector<long long> t, lz;
        segment_tree () {};
        segment_tree (int _n) {
            n = _n;
            t.resize(4 * n + 7);
            lz.resize(4 * n + 7);
        }
        void build(int id, int l, int r) {
            if (l == r) {
                t[id] = d[arr[l]];
                return ;
            }
            int m = (l + r) >> 1;
            build(id << 1, l, m);
            build(id << 1 | 1, m + 1, r);
            t[id] = max(t[id << 1], t[id << 1 | 1]);
        }
        void push(int id) {
            long long &v = lz[id];
            t[id << 1] += v;
            t[id << 1 | 1] += v;
            lz[id << 1] += v;
            lz[id << 1 | 1] += v;
            v = 0;
        }
        void update(int id, int l, int r, int u, int v, long long val) {
            if (l > v or r < u) return ;
            if (l >= u and r <= v) {
                t[id] += val;
                lz[id] += val;
                return ;
            }
            if (lz[id] != 0) push(id);
            int m = (l + r) >> 1;
            update(id << 1, l, m, u, v, val);
            update(id << 1 | 1, m + 1, r, u, v, val);
            t[id] = max(t[id << 1], t[id << 1 | 1]);
        }
        long long getMax(int id, int l, int r, int u, int v) {
            if (l > v or r < u)
                return 0;
            if (l >= u and r <= v)
                return t[id];
            if (lz[id] != 0) push(id);
            int m = (l + r) >> 1;
            return max(getMax(id << 1, l, m, u, v),
                       getMax(id << 1 | 1, m + 1, r, u, v));
        }
        long long get(int id, int l, int r, int p) {
            if (l == r) return t[id];
            if (lz[id] != 0) push(id);
            int m = (l + r) >> 1;
            return (p <= m ? get(id << 1, l, m, p) :
                             get(id << 1 | 1, m + 1, r, p));
        }
        long long get(int x) {
            return get(1, 1, n, x);
        }
        int fx(int id, int l, int r) {
            if (l == r) return arr[l];
            if (lz[id] != 0) push(id);
            int m = (l + r) >> 1;
            if (t[id << 1] >= t[id << 1 | 1])
                return fx(id << 1, l, m);
            return fx(id << 1 | 1, m + 1, r);
        }
    };
    segment_tree st;
    void init() {
        st = segment_tree(2 * n);
        for(int i = 1; i <= n; ++i) {
            arr[tin[i]] = arr[tout[i]] = i;
        }
//        FOR(i, 1, n) cout << d[i] << ' '; cout << nl;
//        FOR(i, 1, 2 * n) cout << arr[i] << ' '; cout << nl;
        st.build(1, 1, 2 * n);
    }
    long long getP(int t) {
        return st.get(1, 1, 2 * n, tin[t]);
    }
    long long get(int u, int t) {
        if (t == -1) {
            return st.getMax(1, 1, 2 * n, tin[u], tout[u]) - 2LL * st.get(tin[u]);
        }
        long long px = -2LL * st.get(tin[u]);
        long long r = 0;
        if (tin[u] != tin[t]) {
            r = max(r, st.getMax(1, 1, 2 * n, tin[u], tin[t] - 1));
        }
        if (tout[t] != tout[u]) {
            r = max(r, st.getMax(1, 1, 2 * n, tout[t] + 1, tout[u]));
        }
        return px + r;
    }
    void update(int l, int r, long long val) {
        st.update(1, 1, 2 * n, l, r, val);
    }
    int fx() {
        return st.fx(1, 1, 2 * n);
    }
};

struct segment_tree {
    // handle point update / get max
    // index theo base
    int n;
    vector<long long> t, lz;
    void init (int _n) {
        n = _n;
        t.resize(4 * n + 7);
        lz.resize(4 * n + 7);
    }
    void push(int id) {
        long long &v = lz[id];
        t[id << 1] += v;
        t[id << 1 | 1] += v;
        lz[id << 1] += v;
        lz[id << 1 | 1] += v;
        v = 0;
    }

    const long long INF = -(long long)1e17;
    void update(int id, int l, int r, int p, long long val) {
        if (l == r) {
            t[id] = val;
            return ;
        }
        if (lz[id]) push(id);
        int m = (l + r) >> 1;
        if (p <= m)
            update(id << 1, l, m, p, val);
        else
            update(id << 1 | 1, m + 1, r, p, val);
        t[id] = max(t[id << 1], t[id << 1 | 1]);
    }
    void update(int p, long long val) {
        update(1, 1, n, p, val);
    }

    void update(int id, int l, int r, int u, int v, long long val) {
        if (l > v or r < u) return ;
        if (l >= u and r <= v) {
            t[id] += val;
            lz[id] += val;
            return ;
        }
        if (lz[id]) push(id);
        int m = (l + r) >> 1;
        update(id << 1, l, m, u, v, val);
        update(id << 1 | 1, m + 1, r, u, v, val);
        t[id] = max(t[id << 1], t[id << 1 | 1]);
    }
    void update(int l, int r, long long val) {
        update(1, 1, n, l, r, val);
    }
    long long get(int id, int l, int r, int u, int v) {
        if (l > v or r < u) return INF;
        if (l >= u and r <= v) return t[id];
        if (lz[id]) push(id);
        int m = (l + r) >> 1;
        return max(get(id << 1, l, m, u, v),
                   get(id << 1 | 1, m + 1, r, u, v));
    }
    long long get(int l, int r) {
        return get(1, 1, n, l, r);
    }

} T;

int mxx[N];
void dfs2(int u, int p) {
    mxx[u] = pos[u];
    for(int id : g[u]) {
        int v = e[id].get(u);
        if (v != p) {
            dfs2(v,u);
            mxx[u]=max(mxx[u], mxx[v]);
        }
    }
}
void main_code() {
    cin >> n >> q >> w;
    for(int i = 1; i < n; ++i) {
        int u, v; long long c;
        cin >> u >> v >> c;
        e[i] = edge(u, v, c);
        g[u].push_back(i);
        g[v].push_back(i);
    }
    euler(1, 0);
    cnt = 0;
    FOR(i, 1, n) nxt[i] = -1;
    hld(1, 0);
    dfs2(1,0);
    IT::init();
    T.init(n);
    for(int i = 1; i <= n; ++i) {
        T.update(pos[i], IT::get(i, nxt[i]));
    }
    long long last = 0;
    FOR(i, 1, n - 1) {
        if (d[e[i].u] > d[e[i].v])
            swap(e[i].u, e[i].v);
    }
//    FOR(i, 1, n) cout << ch[i] << ' '; cout << nl;
//    FOR(i, 0, cc) cout << hd[i] << ' '; cout << nl;
//    return ;
    while (q--) {
        long long dj, ej;
        cin >> dj >> ej;
        dj = (dj + last) % (n - 1);
        ej = (ej + last) % w;
        ++dj; // edge thu dj
        long long vx = ej - e[dj].w;
        e[dj].w = ej;
//        cerr << "dj: " << dj << nl;
//        cerr << "vx: " << vx << nl;
        // update lai da
        int u = e[dj].u, v = e[dj].v;
        IT::update(tin[v], tout[v], vx);


//        if (ch[u] != ch[v]) {
//            T.update(pos[v], IT::get(v, nxt[v]));
//        }
        T.update(pos[v], mxx[v], -vx);
        for(int cur = v; ;) {
            cur = hd[ch[cur]];
            if (cur == 1) break ;
            int p = par[cur];
            T.update(pos[p], IT::get(p, nxt[p]));
            cur = p;
        }
        int k = IT::fx();
//        cerr << k << nl;
        //get cai d cua no luon
        long long dk = IT::getP(k);
//        cerr << "dk: " << dk << nl;
        long long ans = 0;
        for(int cur = k; ;) {
            int a = hd[ch[cur]];
            if (a != cur) {
                ans = max(ans, T.get(pos[a], pos[par[cur]]) + dk);
            }
            if (a == 1) break ;
            int p = par[a];
            ans = max(ans, IT::get(p, a) + dk);
            cur = p;
        }
        cout << ans << nl;
        last = ans;
    }
}


/*     Let the river flows naturally     */

Compilation message (stderr)

diameter.cpp: In function 'void main_code()':
diameter.cpp:335:13: warning: unused variable 'u' [-Wunused-variable]
  335 |         int u = e[dj].u, v = e[dj].v;
      |             ^
diameter.cpp: In function 'int main()':
diameter.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         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