제출 #446258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446258		benedict0724	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	2 ms	460 KiB

diameter

#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--)
    {
        if(i*2 <= n) { dp[i][0] = max(dp[i][0], dp[i*2][0] + v[i*2]); dp[i][1] += dp[i*2][0] + v[i*2];}
        if(i*2+1 <= n) { dp[i][0] = max(dp[i][0], dp[i*2+1][0] + v[i*2+1]); dp[i][1] += 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[d] = e;
        while(now > 1)
        {
            now /= 2;
            dp[now][0] = dp[now][1] = 0;
            dp[now][0] = max(dp[now][0], dp[now*2][0] + v[now*2]); dp[now][1] += dp[now*2][0] + v[now*2];
            dp[now][0] = max(dp[now][0], dp[now*2+1][0] + v[now*2+1]); dp[now][1] += 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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27