oj.uz

Submission #490600

# Submission time Handle Problem Language Result Execution time Memory
490600 2021-11-28T09:24:34 Z radal Dynamic Diameter (CEOI19_diameter) C++14
18 / 100
 261 ms 9536 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
typedef pair<long double,long double> pld;
const long long int N = 1e5+10,mod = 1e9+7,inf = 1e9,sq = 700,sig = 26;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,int k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
vector<pll> adj[N];
int e[N],seg[N*4];
pll E[N];
int dp[N],n;
void dfs(int v){
    for (pll u : adj[v]){
        dfs(u.X);
        dp[v] = max(dp[v],dp[u.X]+e[u.Y]);
    }
}
void build(int l,int r,int v){
    if (r-l == 1){
        for (pll u : adj[l]) seg[v] += dp[u.X]+e[u.Y];
        return;
    }
    int m = (l+r) >> 1;
    build(l,m,2*v);
    build(m,r,2*v+1);
    seg[v] = max(seg[2*v],seg[2*v+1]);
}
void upd(int l,int r,int v,int p){
    if (r-l == 1){
        seg[v] = 0;
        for (pll u : adj[l])
            seg[v] += dp[u.X]+e[u.Y];
        
        return;
    }
    int m = (l+r) >> 1, u = (v << 1);
    if (p < m) upd(l,m,u,p);
    else upd(m,r,u+1,p);
    seg[v] = max(seg[u|1],seg[u]);
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);cout.tie(0);
    int q;
    ll w;
    cin >> n >> q >> w;
    rep(i,0,n-1){
        int u,v;
        ll d;
        cin >> u >> v >> d;
        e[i] = d;
        if (u > v) swap(u,v);
        E[i] = {u,v};
        adj[u].pb({v,i});
    }
    ll last = 0;
    dfs(1);
    build(1,n+1,1);
    while (q--){
        int d;
        ll x;
        cin >> d >> x;
        d = (d+last)%(n-1);
        x = (x+last)%w;
        e[d] = x;
        int v = E[d].X;
        while (v){
            dp[v] = 0;
            for (pll u : adj[v])
                dp[v] = max(dp[v],dp[u.X]+e[u.Y]);
            upd(1,n+1,1,v);
            v >>= 1;
        }
        last = seg[1];
        cout << last << endl;
    }
    return 0;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 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 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2636 KB Output is correct
2 Correct 6 ms 2764 KB Output is correct
3 Correct 24 ms 3324 KB Output is correct
4 Correct 49 ms 4088 KB Output is correct
5 Correct 6 ms 3208 KB Output is correct
6 Correct 11 ms 3452 KB Output is correct
7 Correct 40 ms 3916 KB Output is correct
8 Correct 86 ms 4732 KB Output is correct
9 Correct 25 ms 5196 KB Output is correct
10 Correct 25 ms 5440 KB Output is correct
11 Correct 70 ms 6056 KB Output is correct
12 Correct 108 ms 6876 KB Output is correct
13 Correct 33 ms 7836 KB Output is correct
14 Correct 43 ms 8004 KB Output is correct
15 Correct 96 ms 8804 KB Output is correct
16 Correct 138 ms 9536 KB Output is correct
17 Correct 234 ms 9292 KB Output is correct

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

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