oj.uz

Submission #446258

# Submission time Handle Problem Language Result Execution time Memory
446258 2021-07-21T11:30:07 Z benedict0724 Dynamic Diameter (CEOI19_diameter) C++17
0 / 100
 2 ms 460 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--)
    {
        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.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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