oj.uz

답안 #711325

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711325 2023-03-16T15:13:33 Z SlavicG Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 752 ms 185244 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, c.max_depth});
    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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 144268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 144268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 144284 KB Output is correct
2 Correct 60 ms 144264 KB Output is correct
3 Correct 58 ms 144344 KB Output is correct
4 Correct 73 ms 144488 KB Output is correct
5 Correct 103 ms 145532 KB Output is correct
6 Correct 66 ms 144324 KB Output is correct
7 Correct 62 ms 144468 KB Output is correct
8 Correct 61 ms 144432 KB Output is correct
9 Correct 60 ms 144460 KB Output is correct
10 Correct 84 ms 144860 KB Output is correct
11 Correct 139 ms 145744 KB Output is correct
12 Correct 66 ms 145696 KB Output is correct
13 Correct 63 ms 145840 KB Output is correct
14 Correct 66 ms 145820 KB Output is correct
15 Correct 97 ms 146196 KB Output is correct
16 Correct 161 ms 147312 KB Output is correct
17 Correct 178 ms 168936 KB Output is correct
18 Correct 170 ms 168952 KB Output is correct
19 Correct 169 ms 170676 KB Output is correct
20 Correct 208 ms 171800 KB Output is correct
21 Correct 474 ms 173176 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 144612 KB Output is correct
2 Incorrect 66 ms 144600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 637 ms 173408 KB Output is correct
2 Correct 597 ms 177460 KB Output is correct
3 Correct 603 ms 177548 KB Output is correct
4 Correct 627 ms 177524 KB Output is correct
5 Correct 585 ms 176948 KB Output is correct
6 Correct 639 ms 175204 KB Output is correct
7 Correct 608 ms 180512 KB Output is correct
8 Correct 607 ms 180500 KB Output is correct
9 Correct 669 ms 180508 KB Output is correct
10 Correct 631 ms 180480 KB Output is correct
11 Correct 667 ms 179988 KB Output is correct
12 Correct 610 ms 177388 KB Output is correct
13 Correct 679 ms 185244 KB Output is correct
14 Correct 719 ms 185092 KB Output is correct
15 Correct 689 ms 185152 KB Output is correct
16 Correct 741 ms 185016 KB Output is correct
17 Correct 752 ms 184196 KB Output is correct
18 Correct 711 ms 179184 KB Output is correct
19 Correct 721 ms 185152 KB Output is correct
20 Correct 673 ms 185012 KB Output is correct
21 Correct 744 ms 185136 KB Output is correct
22 Correct 647 ms 185192 KB Output is correct
23 Correct 705 ms 184040 KB Output is correct
24 Correct 669 ms 179088 KB Output is correct

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 144268 KB Output isn't correct
2 Halted 0 ms 0 KB -