Submission #884745

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
884745	2023-12-08T10:24:14 Z	hamidh100	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	256 ms	32600 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;
}

void bemir(){
    ll v = 0;
    for (int i = 1; i <= INT_MAX; i++){
        v += i;
        v %= INT_MAX;
        v += i;
        v %= INT_MAX - 1;
    }
}

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()) bemir();
        auto x = *S.begin();
        S.erase(S.begin());
        if (S.empty()) bemir();
        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	2 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	2 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	10588 KB	Output is correct
2	Correct	2 ms	10680 KB	Output is correct
3	Correct	3 ms	10584 KB	Output is correct
4	Correct	15 ms	10752 KB	Output is correct
5	Correct	51 ms	11108 KB	Output is correct
6	Correct	2 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	10588 KB	Output is correct
10	Correct	16 ms	10844 KB	Output is correct
11	Correct	73 ms	11152 KB	Output is correct
12	Correct	5 ms	11356 KB	Output is correct
13	Correct	5 ms	11348 KB	Output is correct
14	Correct	7 ms	11328 KB	Output is correct
15	Correct	23 ms	11488 KB	Output is correct
16	Correct	95 ms	11640 KB	Output is correct
17	Correct	76 ms	32132 KB	Output is correct
18	Correct	103 ms	32044 KB	Output is correct
19	Correct	80 ms	31940 KB	Output is correct
20	Correct	102 ms	32140 KB	Output is correct
21	Correct	256 ms	32600 KB	Output is correct