oj.uz

Submission #711326

# Submission time Handle Problem Language Result Execution time Memory
711326 2023-03-16T15:15:10 Z SlavicG Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 785 ms 181192 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
#define int long long
 
const int N = 8e5 + 10;
int out[N], in[N], d[N];
vector<int> a;
vector<pair<int, int>> adj[N];
 
void dfs(int u, int par) {
    in[u] = out[u] = sz(a);
    a.pb(u);
    for(auto x: adj[u]) {
        int v = x.first, w = x.second;
        if(v == par) continue;
        d[v] = d[u] + w;
        dfs(v, u);
        out[u] = sz(a);
        a.pb(u);
    }
}
 
struct node {
    int prefix, sufix, ans, max_depth, max_lca;
};
 
node merge(node a, node b) {
    node c;
    c.prefix = max({a.prefix, b.prefix, b.max_depth + a.max_lca});
    c.sufix = max({a.sufix, b.sufix, a.max_depth + b.max_lca});
    c.max_depth = max(a.max_depth, b.max_depth);
    c.max_lca = max(a.max_lca, b.max_lca);
    c.ans = max({a.ans, b.ans, a.sufix + b.max_depth, a.max_depth + b.prefix});
    return c;
}
 
node t[4 * N];
int lazy[4 * N];
 
void push(int i, int l, int r) {
    if(!lazy[i]) return;
    t[i].max_depth += lazy[i];
    t[i].max_lca -= 2 * lazy[i];
    t[i].prefix -= lazy[i];
    t[i].sufix -= lazy[i];
    t[i].ans += lazy[i];
    if(l != r) {
        lazy[2 * i] += lazy[i];
        lazy[2 * i + 1] += lazy[i];
    }
    lazy[i] = 0;
}
void modif(int i, int l, int r, int tl, int tr, int val) {
    push(i, l, r);
    if(l > tr || r < tl) return;
    if(l >= tl && r <= tr) {
        lazy[i] += val;
        push(i, l, r);
        return;
    }
    push(i, l, r);
    int mid = l + r >> 1;
    modif(2 * i, l, mid, tl, tr, val);
    modif(2 * i + 1, mid + 1, r, tl, tr, val);
    t[i] = merge(t[2 * i], t[2 * i + 1]);
}
const int inf = 1e14;
const node neutral = {-inf, -inf, -inf, -inf, -inf};
 
void build(int i, int l, int r) {
    if(l > r) return;
    if(l == r) {
        t[i].max_depth = d[a[l]];
        t[i].max_lca = -2 * d[a[l]];
        t[i].prefix = -inf;
        t[i].sufix = -inf;
        t[i].ans = d[a[l]];
        return;
    }
    int mid = l + r >> 1;
    build(2 * i, l, mid);
    build(2 * i + 1, mid + 1, r);
    t[i] = merge(t[2 * i], t[2 * i + 1]);
}
void solve() {
    a.clear();
    for(int i = 0; i < 4 * N; ++i) t[i] = neutral;
    int n, q, w; cin >> n >> q >> w;
    vector<pair<int, int>> edges;
    map<pair<int, int>, int> mp;
    for(int i = 0; i < n - 1; ++i) {
        int u, v, c; cin >> u >> v >> c; --u, --v;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
        edges.pb({u, v});
        mp[{u, v}] = mp[{v, u}] = c;
    }
    dfs(0, -1);
    for(int i = 0; i < n - 1; ++i) {
        if(in[edges[i].first] > in[edges[i].second]) swap(edges[i].first, edges[i].second);
    }
    build(1, 0, sz(a) - 1);
    int last = 0;
    while(q--) {
        int d, e; cin >> d >> e; d = (d + last) % (n - 1), e = (e + last) % w;
        modif(1, 0, sz(a) - 1, in[edges[d].second], out[edges[d].second], e - mp[{edges[d].first, edges[d].second}]);
        last = max(t[1].ans, t[1].max_depth);
        mp[{edges[d].first, edges[d].second}] = mp[{edges[d].second, edges[d].first}] = e;
        cout << last << "\n";
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

Compilation message

diameter.cpp: In function 'void modif(long long int, long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int mid = l + r >> 1;
      |               ~~^~~
diameter.cpp: In function 'void build(long long int, long long int, long long int)':
diameter.cpp:89:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 144276 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 57 ms 144332 KB Output is correct
2 Correct 58 ms 144344 KB Output is correct
3 Correct 58 ms 144332 KB Output is correct
4 Correct 73 ms 144444 KB Output is correct
5 Correct 110 ms 144776 KB Output is correct
6 Correct 59 ms 144296 KB Output is correct
7 Correct 59 ms 144448 KB Output is correct
8 Correct 59 ms 144412 KB Output is correct
9 Correct 58 ms 144504 KB Output is correct
10 Correct 72 ms 144624 KB Output is correct
11 Correct 136 ms 144900 KB Output is correct
12 Correct 72 ms 145648 KB Output is correct
13 Correct 63 ms 145728 KB Output is correct
14 Correct 63 ms 145840 KB Output is correct
15 Correct 79 ms 145832 KB Output is correct
16 Correct 151 ms 146264 KB Output is correct
17 Correct 157 ms 167676 KB Output is correct
18 Correct 151 ms 167788 KB Output is correct
19 Correct 155 ms 169512 KB Output is correct
20 Correct 208 ms 170400 KB Output is correct
21 Correct 407 ms 170880 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 144540 KB Output is correct
2 Incorrect 73 ms 144640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 173444 KB Output is correct
2 Correct 641 ms 173496 KB Output is correct
3 Correct 597 ms 173412 KB Output is correct
4 Correct 604 ms 173420 KB Output is correct
5 Correct 670 ms 173060 KB Output is correct
6 Correct 537 ms 171132 KB Output is correct
7 Correct 603 ms 176420 KB Output is correct
8 Correct 636 ms 176484 KB Output is correct
9 Correct 634 ms 176480 KB Output is correct
10 Correct 607 ms 176400 KB Output is correct
11 Correct 630 ms 175836 KB Output is correct
12 Correct 586 ms 173212 KB Output is correct
13 Correct 726 ms 181156 KB Output is correct
14 Correct 755 ms 181112 KB Output is correct
15 Correct 689 ms 181076 KB Output is correct
16 Correct 680 ms 181192 KB Output is correct
17 Correct 785 ms 180084 KB Output is correct
18 Correct 592 ms 174864 KB Output is correct
19 Correct 732 ms 181012 KB Output is correct
20 Correct 686 ms 181128 KB Output is correct
21 Correct 744 ms 181080 KB Output is correct
22 Correct 732 ms 180916 KB Output is correct
23 Correct 672 ms 179996 KB Output is correct
24 Correct 634 ms 174952 KB Output is correct

Subtask #6
0 / 27.0

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