Submission #884739

#	Time	Username	Problem	Language	Result	Execution time	Memory
884739		hamidh100	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	266 ms	31340 KiB

diameter

/* In the name of God */

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
#define PB push_back
#define MP make_pair
#define all(a) (a).begin(), (a).end()
#define endl '\n'
#define dbg(x) cerr << '[' << #x << ": " << x << "]\n"
#define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"

const ll INF = (ll)2e18 + 1386;
const ld EPS = 0.000000000000001;
const int MOD = 1e9 + 7;

inline int _add(int a, int b){ int res = a + b; return (res >= MOD ? res - MOD : res); }
inline int _neg(int a, int b){ int res = (abs(a - b) < MOD ? a - b : (a - b) % MOD); return (res < 0 ? res + MOD : res); }
inline int _mlt(ll a, ll b){ return (a * b % MOD); }
inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); }

const int MAXN = 1e5 + 5, LG = 20;

int h[MAXN], par[MAXN][LG];
int st[MAXN], et[MAXN], timer = 1;
ll wei[MAXN];
ll dp[MAXN];
vector<PII> N[MAXN];
VI ord = {23};

void dfs_ini(int v, int p){
    ord.PB(v);
    st[v] = timer++;
    for (auto [u, e] : N[v]){
        if (u == p) continue;
        h[u] = h[v] + 1;
        par[u][0] = v;
        for (int i = 1; i < LG; i++){
            par[u][i] = par[par[u][i - 1]][i - 1];
        }
        dp[u] = dp[v] + wei[e];
        dfs_ini(u, v);
    }
    et[v] = timer;
}

PII edg[MAXN];

ll seg[MAXN << 2], laz[MAXN << 2];
#define lc id << 1
#define rc id << 1 | 1

void build(int id, int l, int r){
    if (r - l == 1){
        seg[id] = dp[ord[l]];
        return;
    }
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid, r);
    seg[id] = max(seg[lc], seg[rc]);
}

void shift(int id, int l, int r){
    laz[lc] += laz[id];
    laz[rc] += laz[id];
    seg[lc] += laz[id];
    seg[rc] += laz[id];
    laz[id] = 0;
}

void upd(int id, int l, int r, int ql, int qr, ll val){
    if (ql >= r || qr <= l) return;
    if (l >= ql && r <= qr){
        seg[id] += val;
        laz[id] += val;
        return;
    }
    int mid = l + r >> 1;
    shift(id, l, r);
    upd(lc, l, mid, ql, qr, val);
    upd(rc, mid, r, ql, qr, val);
    seg[id] = max(seg[lc], seg[rc]);
}

ll get(int id, int l, int r, int ql, int qr){
    if (ql >= r || qr <= l) return 0;
    if (l >= ql && r <= qr) return seg[id];
    int mid = l + r >> 1;
    shift(id, l, r);
    return max(get(lc, l, mid, ql, qr), get(rc, mid, r, ql, qr));
}

int goo(int v, int k){
    for (int i = 0; i < LG; i++){
        if (k >> i & 1) v = par[v][i];
    }
    return v;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q, w;
    cin >> n >> q >> w;
    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v >> wei[i];
        N[u].PB(MP(v, i));
        N[v].PB(MP(u, i));
        edg[i] = MP(u, v);
    }
    for (int i = 0; i < LG; i++) par[1][i] = 1;
    dfs_ini(1, 0);
    build(1, 1, n + 1);
    set<pair<ll, int>> S;
    S.insert(MP(0, 0));
    for (auto [u, e] : N[1]){
        ll val = get(1, 1, n + 1, st[u], et[u]);
        S.insert(MP(-val, u));
        //dbg2(u, get(1, 1, n + 1, st[u], et[u]));
    }
    //dbg("ADF");
    //for (auto [x, y] : S) dbg2(-x, y);
    ll lst = 0;
    while (q--){
        ll d, e;
        cin >> d >> e;
        (d += lst) %= (n - 1);
        (e += lst) %= w;
        d++;
        int v = (h[edg[d].first] < h[edg[d].second] ? edg[d].first : edg[d].second);
        int u = edg[d].first + edg[d].second - v;
        int bache = goo(u, h[u] - h[1] - 1);
        ll prvbache = get(1, 1, n + 1, st[bache], et[bache]);
        S.erase(MP(-prvbache, bache));
        upd(1, 1, n + 1, st[u], et[u], e - wei[d]);
        ll cur = get(1, 1, n + 1, st[bache], et[bache]);
        S.insert(MP(-cur, bache));
        //for (auto [x, y] : S) dbg2(-x, y);
        if (S.empty()) break;
        auto x = *S.begin();
        S.erase(S.begin());
        if (S.empty()) break;
        ll ans = -x.first + -(*S.begin()).first;
        cout << ans << endl;
        //dbg(ans);
        lst = ans;
        S.insert(x);
        wei[d] = e;
        /*dbg(goo(u, h[u] - h[1] - 1));
        for (auto [u, e] : N[1]){
            dbg2(u, get(1, 1, n + 1, st[u], et[u]));
        }
        dbg("ADF");*/
        //lst = dp[1][0];
    }
    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void build(int, int, int)':
diameter.cpp:67:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |     int mid = l + r >> 1;
      |               ~~^~~
diameter.cpp: In function 'void upd(int, int, int, int, int, ll)':
diameter.cpp:88:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |     int mid = l + r >> 1;
      |               ~~^~~
diameter.cpp: In function 'll get(int, int, int, int, int)':
diameter.cpp:98:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |     int mid = l + r >> 1;
      |               ~~^~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27