oj.uz

Submission #490599

# Submission time Handle Problem Language Result Execution time Memory
490599 2021-11-28T09:23:43 Z radal Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 326 ms 58188 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 = 8e5+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;
}
ll seg[4*N],lz[4*N];
ll h[N];
ll e[N];
pll a[N];
int par[N][20],T,tin[N],tout[N],b[N],l[N];
vector<pair<int,ll>> adj[N];
void dfs(int v,int p){
    par[v][0] = p;
    tin[v] = T;
    b[T] = v;
    T++;
    for (auto u : adj[v]){
        if (u.X == p) continue;
        h[u.X] = u.Y+h[v];
        l[u.X] = l[v]+1;
        dfs(u.X,v);
    }
    tout[v] = T;
    b[T] = v;
    T++;
}
void build(int l,int r,int v){
    if (r-l == 1){
        seg[v] = h[b[l]];
        return;
    }
    int m = (l+r) >> 1,u = (v << 1);
    build(l,m,u);
    build(m,r,u|1);
    seg[v] = max(seg[u],seg[u|1]);
}
void upd(int l,int r,int s,int e,ll x,int v = 1){
    if (l >= s && e >= r){
        seg[v] += x;
        lz[v] += x;
        return;
    }
    if (l >= e || s >= r) return;
    int m = (l+r) >> 1,u = (v << 1);
    if (lz[v]){
        lz[u] += lz[v];
        lz[u|1] += lz[v];
        seg[u] += lz[v];
        seg[u|1] += lz[v];
        lz[v] = 0;
    }
    upd(l,m,s,e,x,u);
    upd(m,r,s,e,x,u|1);
    seg[v] = max(seg[u],seg[u|1]);
}
ll que(int l,int r,int s,int e,int v = 1){
    if (l >= s && e >= r)
        return seg[v];
    if (l >= e || s >= r) return 0;
    int m = (l+r) >> 1,u = (v << 1);
    if (lz[v]){
        lz[u] += lz[v];
        lz[u|1] += lz[v];
        seg[u] += lz[v];
        seg[u|1] += lz[v];
        lz[v] = 0;
    }
    return max(que(l,m,s,e,u),que(m,r,s,e,u|1));
}
inline int getpar(int v,int k){
    repr(i,19,0){
        if (k >= (1 << i)){
            k -= (1 << i);
            v = par[v][i];
        }
    }
    return v;
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);cout.tie(0);
    int n,q;
    ll w;
    cin >> n >> q >> w;
    rep(i,0,n-1){
        int u,v;
        ll d;
        cin >> u >> v >> d;
        e[i] = d;
        a[i] = {u,v};
        adj[u].pb({v,d});
        adj[v].pb({u,d});
    }
    dfs(1,0);
    rep(i,0,n-1) if (par[a[i].X][0] == a[i].Y) swap(a[i].X,a[i].Y);
    rep(j,1,20)
        rep(i,2,n+1)
            par[i][j] = par[par[i][j-1]][j-1];
    ll last = 0;
    build(0,T,1);
    multiset<ll> st;
    for (pll u : adj[1])
        st.insert(que(0,T,tin[u.X],tout[u.X]+1));
    while (q--){
        int d;
        ll x;
        cin >> d >> x;
        d = (d+last)%(n-1);
        x = (x+last)%w;
        ll y = a[d].Y;
        int v = getpar(y,l[y]-1);
        st.erase(st.find(que(0,T,tin[v],tout[v]+1)));
        upd(0,T,tin[y],tout[y]+1,x-e[d]);
        st.insert(que(0,T,tin[v],tout[v]+1));
        e[d] = x;
        auto it = st.rbegin();
        last = (*it);
        y = last;
        st.erase(st.find(last));
        if (st.empty()){
            cout << last << endl;
            st.insert(y);
            continue;
        }
        it = st.rbegin();
        last += (*it);
        st.insert(y);
        cout << last << endl;
    }
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19148 KB Output is correct
2 Correct 10 ms 19148 KB Output is correct
3 Correct 10 ms 19124 KB Output is correct
4 Correct 20 ms 19404 KB Output is correct
5 Correct 63 ms 20220 KB Output is correct
6 Correct 10 ms 19148 KB Output is correct
7 Correct 11 ms 19244 KB Output is correct
8 Correct 10 ms 19276 KB Output is correct
9 Correct 12 ms 19316 KB Output is correct
10 Correct 24 ms 19532 KB Output is correct
11 Correct 82 ms 20644 KB Output is correct
12 Correct 14 ms 20556 KB Output is correct
13 Correct 13 ms 20796 KB Output is correct
14 Correct 15 ms 20736 KB Output is correct
15 Correct 31 ms 21044 KB Output is correct
16 Correct 106 ms 22236 KB Output is correct
17 Correct 90 ms 46128 KB Output is correct
18 Correct 104 ms 46640 KB Output is correct
19 Correct 104 ms 48560 KB Output is correct
20 Correct 124 ms 49404 KB Output is correct
21 Correct 310 ms 50760 KB Output is correct

Subtask #4
0 / 18.0

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

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 50440 KB Output is correct
2 Correct 259 ms 50328 KB Output is correct
3 Correct 224 ms 50352 KB Output is correct
4 Correct 245 ms 50384 KB Output is correct
5 Correct 248 ms 50292 KB Output is correct
6 Correct 260 ms 50644 KB Output is correct
7 Correct 245 ms 53376 KB Output is correct
8 Correct 252 ms 53452 KB Output is correct
9 Correct 244 ms 53444 KB Output is correct
10 Correct 253 ms 53480 KB Output is correct
11 Correct 281 ms 53316 KB Output is correct
12 Correct 284 ms 52540 KB Output is correct
13 Correct 282 ms 58056 KB Output is correct
14 Correct 273 ms 58144 KB Output is correct
15 Correct 284 ms 58176 KB Output is correct
16 Correct 294 ms 58008 KB Output is correct
17 Correct 286 ms 57468 KB Output is correct
18 Correct 307 ms 54396 KB Output is correct
19 Correct 279 ms 58092 KB Output is correct
20 Correct 279 ms 58092 KB Output is correct
21 Correct 294 ms 58188 KB Output is correct
22 Correct 284 ms 58060 KB Output is correct
23 Correct 320 ms 57468 KB Output is correct
24 Correct 326 ms 54316 KB Output is correct

Subtask #6
0 / 27.0

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