Submission #446261

#	Time	Username	Problem	Language	Result	Execution time	Memory
446261		benedict0724	Dynamic Diameter (CEOI19_diameter)	C++17	18 / 100	330 ms	6036 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--)
    {
        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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27