oj.uz

Submission #472634

# Submission time Handle Problem Language Result Execution time Memory
472634 2021-09-13T23:36:32 Z Ozy Dynamic Diameter (CEOI19_diameter) C++17
0 / 100
 454 ms 8052 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000

lli n,q,w,a,b,c,last,id,lim;
lli peso[MAX+2];
pair<lli,lli> arr[MAX+2];

multiset<lli> raices;
multiset<lli>::iterator it;
lli prof[(2*MAX)+2],padres[(2*MAX)+2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q >> w;
    rep(i,1,n-1) {
        cin >> a >> b >> c;
        arr[i] = {a,b};
        peso[i] = c;

        if (a > b) swap(a,b);
        padres[b] = c;
    }

    repa(i,(n/2)+1,1) {
        a = prof[i*2] + padres[i*2];
        if ((i*2)+1 <= n) b = prof[(i*2)+1] + padres[(i*2)+1];
        else b = 0;

        prof[i] = max(a,b);

        c = a+b;
        raices.insert(-c);


    }

    lim = 1ll << 62;
    rep(i,1,q) {

        //correcto
        cin >> id >> c;
        id += last;
        id %= (n-1);
        id++;
        c += last;
        c %= w;

        a = arr[id].first;
        b = arr[id].second;

        //fill

        if (a > b) swap(a,b);
        padres[b] = c;

        lli x,y;
        while (a > 0) {

            x = prof[(a*2)] + prof[(a*2)+1] + padres[(a*2)] + padres[(a*2)+1];
            it = raices.lower_bound(-x);
            raices.erase(it);

            x = prof[a*2] + padres[a*2];
            y = prof[(a*2)+1] + padres[(a*2)+1];

            prof[a] = max(x,y);

            x += y;
            raices.insert(-x);

            b = a;
            a /= 2;
        }

        a = *raices.lower_bound(-lim);
        a *= -1;
        cout << a << "\n";
        last = a;
    }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -