oj.uz

Submission #884749

# Submission time Handle Problem Language Result Execution time Memory
884749 2023-12-08T10:40:29 Z hamidh100 Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 241 ms 34760 KB 
/* 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;
    ll 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);
        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 10584 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 10584 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 1 ms 10588 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 11 ms 10756 KB Output is correct
5 Correct 51 ms 11092 KB Output is correct
6 Correct 2 ms 10584 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 83 ms 11092 KB Output is correct
12 Correct 5 ms 11356 KB Output is correct
13 Correct 5 ms 11356 KB Output is correct
14 Correct 6 ms 11352 KB Output is correct
15 Correct 23 ms 11352 KB Output is correct
16 Correct 96 ms 11856 KB Output is correct
17 Correct 76 ms 32104 KB Output is correct
18 Correct 82 ms 32196 KB Output is correct
19 Correct 79 ms 31996 KB Output is correct
20 Correct 104 ms 32200 KB Output is correct
21 Correct 227 ms 32644 KB Output is correct

Subtask #4
0 / 18.0

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

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 27084 KB Output is correct
2 Correct 191 ms 27248 KB Output is correct
3 Correct 185 ms 27196 KB Output is correct
4 Correct 182 ms 27340 KB Output is correct
5 Correct 191 ms 27816 KB Output is correct
6 Correct 192 ms 30284 KB Output is correct
7 Correct 178 ms 30072 KB Output is correct
8 Correct 198 ms 30064 KB Output is correct
9 Correct 220 ms 30172 KB Output is correct
10 Correct 198 ms 30132 KB Output is correct
11 Correct 210 ms 30308 KB Output is correct
12 Correct 228 ms 32368 KB Output is correct
13 Correct 182 ms 34504 KB Output is correct
14 Correct 241 ms 34452 KB Output is correct
15 Correct 223 ms 34504 KB Output is correct
16 Correct 215 ms 34548 KB Output is correct
17 Correct 230 ms 34252 KB Output is correct
18 Correct 209 ms 33872 KB Output is correct
19 Correct 181 ms 34508 KB Output is correct
20 Correct 181 ms 34760 KB Output is correct
21 Correct 215 ms 34552 KB Output is correct
22 Correct 208 ms 34252 KB Output is correct
23 Correct 219 ms 34252 KB Output is correct
24 Correct 217 ms 33872 KB Output is correct

Subtask #6
0 / 27.0

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