oj.uz

답안 #472635

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
472635 2021-09-13T23:50:12 Z Ozy Dynamic Diameter (CEOI19_diameter) C++17
18 / 100
 640 ms 9820 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], dia[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) {
        a = prof[i*2] + padres[i*2];
        b = prof[(i*2)+1] + padres[(i*2)+1];

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

        c = a+b;
        dia[i] = c;
        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 = dia[a];
            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;
            dia[a] = x;
            raices.insert(-x);

            b = a;
            a /= 2;
        }

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

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 7.0

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

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 11 ms 460 KB Output is correct
3 Correct 52 ms 860 KB Output is correct
4 Correct 110 ms 1148 KB Output is correct
5 Correct 6 ms 1100 KB Output is correct
6 Correct 21 ms 1348 KB Output is correct
7 Correct 80 ms 1604 KB Output is correct
8 Correct 154 ms 2560 KB Output is correct
9 Correct 23 ms 4216 KB Output is correct
10 Correct 44 ms 4392 KB Output is correct
11 Correct 130 ms 4956 KB Output is correct
12 Correct 225 ms 5876 KB Output is correct
13 Correct 48 ms 8132 KB Output is correct
14 Correct 68 ms 8260 KB Output is correct
15 Correct 163 ms 8984 KB Output is correct
16 Correct 286 ms 9820 KB Output is correct
17 Correct 640 ms 9556 KB Output is correct

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

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