oj.uz

Submission #578812

# Submission time Handle Problem Language Result Execution time Memory
578812 2022-06-18T04:47:43 Z talant117408 Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 524 ms 38232 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int N = 1e5+7;
set <pair <int, ll>> graph[N];
vector <pair <pii, ll>> edges;
ll df, vf;
int n, q;
ll w;

void find_furthest(int v, int p, ll dist = 0) {
    if (dist > df) {
        df = dist;
        vf = v;
    }
    for (auto to : graph[v]) {
        if (to.first == p) continue;
        find_furthest(to.first, v, dist+to.second);
    }
}

void subtask3() {
    for (auto to : edges) {
        if (to.first.first != 1) {
            return;
        }
    }
    set <pair <ll, int>, greater <pair <ll, int>>> st;
    for (auto to : edges) {
        st.insert(mp(to.second, to.first.second));
    }
    ll last = 0;
    while (q--) {
        ll d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;
        auto &c = edges[d].second;
        auto b = edges[d].first.second;
        st.erase(st.find(mp(c, b)));
        c = e;
        st.insert(mp(c, b));
        ll ans = 0;
        ll cnt = 0;
        for (auto to : st) {
            ans += to.first;
            if (++cnt > 1) break;
        }
        cout << ans << endl;
        last = ans;
    }
    exit(0);
}

void subtask4() {
    vector <ll> ans_for(n+1);
    vector <pll> mx_child(n+1), dist_child(n+1);
    set <pair <ll, int>, greater <pair <ll, int>>> st;
    for (auto to : edges) {
        auto a = to.first.first;
        auto b = to.first.second;
        if (!(a*2 != b || a*2+1 != b)) {
            return;
        }
        if (a*2 == b) dist_child[a].first = to.second;
        else dist_child[a].second = to.second;
    }
    
    for (int i = 1; i <= n; i++) {
        if (sz(graph[i]) == 1) {
            int x = i;
            while (x) {
                if (x*2 <= n) mx_child[x].first = max(mx_child[x*2].first, mx_child[x*2].second)+dist_child[x].first;
                if (x*2+1 <= n) mx_child[x].second = max(mx_child[x*2+1].first, mx_child[x*2+1].second)+dist_child[x].second;
                x >>= 1;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        st.insert(mp(mx_child[i].first+mx_child[i].second, i));
    }
    
    ll last = 0;
    while (q--) {
        ll d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;
        auto a = edges[d].first.first, b = edges[d].first.second;
        int x = (b >> 1);
        if (a*2 == b) dist_child[a].first = e;
        else dist_child[a].second = e;
        while (x) {
            st.erase(st.find(mp(mx_child[x].first+mx_child[x].second, x)));
            if (x*2 <= n) mx_child[x].first = max(mx_child[x*2].first, mx_child[x*2].second)+dist_child[x].first;
            if (x*2+1 <= n) mx_child[x].second = max(mx_child[x*2+1].first, mx_child[x*2+1].second)+dist_child[x].second;
            st.insert(mp(mx_child[x].first+mx_child[x].second, x));
            x >>= 1;
        }
        cout << (*st.begin()).first << endl;
        last = (*st.begin()).first;
    }
    exit(0);
}

ll tree[N*4], lz[N*4];
int depth[N], timer;
pii range[N];
int parent[N];
int origin = 1;

void push(int v, int l, int r) {
    if (lz[v] != 0) {
        tree[v] += lz[v];
        if (l != r) {
            lz[v*2] += lz[v];
            lz[v*2+1] += lz[v];
        }
        lz[v] = 0;
    }
}

void update(int v, int l, int r, int ql, int qr, ll val) {
    push(v, l, r);
    if (ql > r || l > qr) return;
    if (ql <= l && r <= qr) {
        lz[v] += val;
        push(v, l, r);
        return;
    }
    int mid = (l+r) >> 1;
    update(v*2, l, mid, ql, qr, val);
    update(v*2+1, mid+1, r, ql, qr, val);
    tree[v] = max(tree[v*2], tree[v*2+1]);
}

ll get(int v, int l, int r, int ql, int qr) {
    push(v, l, r);
    if (ql > r || l > qr) return -1e18;
    if (ql <= l && r <= qr) return tree[v];
    int mid = (l+r) >> 1;
    return max(get(v*2, l, mid, ql, qr), get(v*2+1, mid+1, r, ql, qr));
}

void dfs(int v = 1, int p = 1, ll dist = 0) {
    range[v].first = ++timer;
    update(1, 1, n, timer, timer, dist);
    parent[v] = origin;
    for (auto to : graph[v]) {
        if (to.first == p) continue;
        depth[to.first] = depth[v] + 1;
        if (v == 1) origin = to.first;
        dfs(to.first, v, dist+to.second);
    }
    range[v].second = timer;
}

void solve() {
    cin >> n >> q >> w;
    for (int i = 0; i < n-1; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        if (a > b) swap(a, b);
        edges.pb(mp(mp(a, b), c));
        graph[a].insert(mp(b, c));
        graph[b].insert(mp(a, c));
    }
    
    //~ if (n <= 5000) {
        //~ ll last = 0;
        //~ while (q--) {
            //~ ll d, e;
            //~ cin >> d >> e;
            //~ d = (d + last) % (n - 1);
            //~ e = (e + last) % w;
            //~ auto a = edges[d].first.first, b = edges[d].first.second;
            //~ auto &c = edges[d].second;
            //~ graph[a].erase(graph[a].find(mp(b, c)));
            //~ graph[b].erase(graph[b].find(mp(a, c)));
            //~ c = e;
            //~ graph[a].insert(mp(b, c));
            //~ graph[b].insert(mp(a, c));
            //~ df = vf = 0;
            //~ find_furthest(1, 1);
            //~ df = 0;
            //~ find_furthest(vf, vf);
            //~ cout << df << endl;
            //~ last = df;
        //~ }
        //~ return;
    //~ }
    //~ subtask3();
    //~ subtask4();
    
    dfs();
    set <pair <ll, int>, greater <pair <ll, int>>> st;
    for (auto to : graph[1]) {
        st.insert(mp(get(1, 1, n, range[to.first].first, range[to.first].second), to.first));
    }
    ll last = 0;
    while (q--) {
        ll d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;
        auto a = edges[d].first.first, b = edges[d].first.second;
        auto &c = edges[d].second;
        if (depth[a] > depth[b]) swap(a, b);
        st.erase(st.find(mp(get(1, 1, n, range[parent[b]].first, range[parent[b]].second), parent[b])));
        update(1, 1, n, range[b].first, range[b].second, e-c);
        c = e;
        st.insert(mp(get(1, 1, n, range[parent[b]].first, range[parent[b]].second), parent[b]));
        ll res = 0;
        ll cnt = 0;
        for (auto to : st) {
            res += to.first;
            if (++cnt > 1) break;
        }
        cout << res << endl;
        last = res;
    }
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}
/*

*/

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 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 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 14 ms 5136 KB Output is correct
5 Correct 61 ms 5384 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5092 KB Output is correct
8 Correct 3 ms 5148 KB Output is correct
9 Correct 7 ms 5076 KB Output is correct
10 Correct 21 ms 5248 KB Output is correct
11 Correct 99 ms 5572 KB Output is correct
12 Correct 9 ms 6268 KB Output is correct
13 Correct 10 ms 6288 KB Output is correct
14 Correct 11 ms 6352 KB Output is correct
15 Correct 33 ms 6448 KB Output is correct
16 Correct 116 ms 6864 KB Output is correct
17 Correct 154 ms 30536 KB Output is correct
18 Correct 193 ms 30532 KB Output is correct
19 Correct 165 ms 30492 KB Output is correct
20 Correct 187 ms 30620 KB Output is correct
21 Correct 437 ms 31144 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5204 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 281 ms 26372 KB Output is correct
2 Correct 360 ms 30412 KB Output is correct
3 Correct 313 ms 30404 KB Output is correct
4 Correct 317 ms 30440 KB Output is correct
5 Correct 386 ms 30996 KB Output is correct
6 Correct 472 ms 33348 KB Output is correct
7 Correct 296 ms 33404 KB Output is correct
8 Correct 354 ms 33380 KB Output is correct
9 Correct 289 ms 33340 KB Output is correct
10 Correct 378 ms 33416 KB Output is correct
11 Correct 378 ms 33880 KB Output is correct
12 Correct 388 ms 35500 KB Output is correct
13 Correct 366 ms 38212 KB Output is correct
14 Correct 340 ms 38204 KB Output is correct
15 Correct 443 ms 38124 KB Output is correct
16 Correct 399 ms 38216 KB Output is correct
17 Correct 431 ms 37964 KB Output is correct
18 Correct 524 ms 37244 KB Output is correct
19 Correct 308 ms 38160 KB Output is correct
20 Correct 287 ms 38132 KB Output is correct
21 Correct 369 ms 38232 KB Output is correct
22 Correct 369 ms 38208 KB Output is correct
23 Correct 398 ms 37968 KB Output is correct
24 Correct 388 ms 37208 KB Output is correct

Subtask #6
0 / 27.0

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