Submission #884739

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
884739	2023-12-08T10:04:04 Z	hamidh100	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	266 ms	31340 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 = 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

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	10588 KB	Output is correct
3	Correct	2 ms	10588 KB	Output is correct
4	Correct	11 ms	10804 KB	Output is correct
5	Correct	50 ms	10976 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	10588 KB	Output is correct
10	Correct	16 ms	10808 KB	Output is correct
11	Correct	72 ms	11172 KB	Output is correct
12	Correct	4 ms	11356 KB	Output is correct
13	Correct	5 ms	11356 KB	Output is correct
14	Correct	6 ms	11356 KB	Output is correct
15	Correct	22 ms	11420 KB	Output is correct
16	Correct	92 ms	11860 KB	Output is correct
17	Correct	89 ms	30804 KB	Output is correct
18	Correct	86 ms	30844 KB	Output is correct
19	Correct	78 ms	30880 KB	Output is correct
20	Correct	108 ms	30916 KB	Output is correct
21	Correct	266 ms	31340 KB	Output is correct