Submission #884740

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
884740	2023-12-08T10:12:57 Z	hamidh100	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	243 ms	32628 KB

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 = 23;

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++;
        if (d <= 0 || d >= n) break;
        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);
        auto x = *S.begin();
        S.erase(S.begin());
        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

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.0

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

Subtask #2
0 / 13.0

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

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	3 ms	10588 KB	Output is correct
4	Correct	13 ms	10596 KB	Output is correct
5	Correct	51 ms	10916 KB	Output is correct
6	Correct	1 ms	10588 KB	Output is correct
7	Correct	2 ms	10588 KB	Output is correct
8	Correct	2 ms	10588 KB	Output is correct
9	Correct	3 ms	10584 KB	Output is correct
10	Correct	16 ms	10844 KB	Output is correct
11	Correct	74 ms	11164 KB	Output is correct
12	Correct	5 ms	11356 KB	Output is correct
13	Correct	5 ms	11356 KB	Output is correct
14	Correct	7 ms	11196 KB	Output is correct
15	Correct	23 ms	11504 KB	Output is correct
16	Correct	95 ms	11684 KB	Output is correct
17	Correct	78 ms	31936 KB	Output is correct
18	Correct	76 ms	31940 KB	Output is correct
19	Correct	81 ms	31944 KB	Output is correct
20	Correct	105 ms	32196 KB	Output is correct
21	Correct	243 ms	32628 KB	Output is correct