oj.uz

답안 #446261

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446261 2021-07-21T11:35:09 Z benedict0724 Dynamic Diameter (CEOI19_diameter) C++17
18 / 100
 330 ms 6036 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pl;

int v[200002], E[100002];
int dp[200002][2];
int tree[400002];
int init(int i, int l, int r){
    if(l == r) return tree[i] = dp[l][1];
    int m = (l + r)/2;
    return tree[i] = max(init(i*2, l, m), init(i*2+1, m+1, r));
}

void update(int i, int l, int r, int id, int val){
    if(l == r) { tree[i] = val; return; }
    int m = (l + r)/2;
    if(id <= m) update(i*2, l, m, id, val);
    else update(i*2+1, m+1, r, id, val);
    tree[i] = max(tree[i*2], tree[i*2+1]);
}

int query() { return tree[1]; }

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    int n, q, w; cin >> n >> q >> w;
    for(int i=0;i<n-1;i++)
    {
        int a, b, c; cin >> a >> b >> c;
        if(a > b) swap(a, b);
        E[i] = b;
        v[b] = c;
    }

    for(int i=n;i>=1;i--)
    {
        dp[i][0] = max(dp[i*2][0] + v[i*2], dp[i*2+1][0] + v[i*2+1]);
        dp[i][1] = dp[i*2][0] + v[i*2] + dp[i*2+1][0] + v[i*2+1];
    }

    init(1, 1, n);

    int last = 0;
    for(int i=1;i<=q;i++)
    {
        int d, e; cin >> d >> e;
        d = (d + last)%(n-1);
        e = (e + last)%w;

        int now = E[d];
        v[now] = e;
        while(now > 1)
        {
            now /= 2;
            dp[now][0] = max(dp[now*2][0] + v[now*2], dp[now*2+1][0] + v[now*2+1]);
            dp[now][1] = dp[now*2][0] + v[now*2] + dp[now*2+1][0] + v[now*2+1];
            update(1, 1, n, now, dp[now][1]);
        }

        last = query();
        cout << last << "\n";
    }
}

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 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 8 ms 460 KB Output is correct
3 Correct 42 ms 964 KB Output is correct
4 Correct 69 ms 1408 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 14 ms 880 KB Output is correct
7 Correct 57 ms 1420 KB Output is correct
8 Correct 113 ms 2204 KB Output is correct
9 Correct 19 ms 2312 KB Output is correct
10 Correct 33 ms 2516 KB Output is correct
11 Correct 86 ms 3176 KB Output is correct
12 Correct 159 ms 3952 KB Output is correct
13 Correct 33 ms 4464 KB Output is correct
14 Correct 47 ms 4552 KB Output is correct
15 Correct 115 ms 5300 KB Output is correct
16 Correct 186 ms 6036 KB Output is correct
17 Correct 330 ms 5916 KB Output is correct

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
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 -