oj.uz

Submission #259944

# Submission time Handle Problem Language Result Execution time Memory
259944 2020-08-08T20:41:22 Z doowey Dynamic Diameter (CEOI19_diameter) C++14
18 / 100
 5000 ms 995736 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const ll N = (ll)1e5 + 5;
ll ww[N];
vector<pii> T[N];

struct Edge{
    ll id;
    ll op_l;
    ll op_r;
    ll el;
    ll er;
};

vector<Edge> G[N];
const ll M = (ll)1e7;

struct Node{
    ll val;
    ll lazy;
};

multiset<ll> all_di;

struct Centroid{
    set<pii> best;
    vector<Node> Tree;
    ll CURN;
    void init(ll n){
        CURN = n;
        for(ll i = 0 ; i <= n * 4 + 12; i ++) {
            Tree.push_back({0,0});
        }
    }
    void push(ll node, ll cl, ll cr){
        Tree[node].val += Tree[node].lazy;
        if(cl != cr){
            Tree[node * 2].lazy += Tree[node].lazy;
            Tree[node * 2 + 1].lazy += Tree[node].lazy;
        }
        Tree[node].lazy = 0;
    }
    void upd(ll node, ll cl, ll cr, ll tl, ll tr, ll v){
        push(node, cl, cr);
        if(cr < tl)
            return;
        if(cl > tr)
            return;
        if(cl >= tl && cr <= tr){
            Tree[node].lazy += v;
            push(node, cl, cr);
            return;
        }
        ll mid = (cl + cr) / 2;
        upd(node * 2, cl, mid, tl, tr, v);
        upd(node * 2 + 1, mid + 1, cr, tl, tr, v);
        Tree[node].val = max(Tree[node * 2].val, Tree[node * 2 + 1].val);
    }
    ll get(ll node, ll cl, ll cr, ll tl, ll tr){
        push(node, cl, cr);
        if(cr < tl)
            return 0ll;
        if(cl > tr)
            return 0ll;
        if(cl >= tl && cr <= tr){
            return Tree[node].val;
        }
        ll mid = (cl + cr) / 2;
        return max(get(node * 2, cl, mid, tl, tr), get(node * 2 + 1, mid + 1, cr, tl, tr));
    }
    void check(ll mode){
        ll sum = 0;
        auto it = best.end();
        for(ll j = 0 ; j < 2; j ++ ){
            if(it != best.begin()){
                it -- ;
                sum += it->fi;
            }
        }
        if(mode == 1){
            all_di.insert(sum);
        }
        else{
            all_di.erase(sum);
        }
    }
};

Centroid shi[M];
ll idccc = 0;

bool ban[N];
ll subt[N];

void dfs1(ll u, ll par){
    subt[u]=1;
    for(auto x : T[u]){
        if(ban[x.fi] || x.fi == par) continue;
        dfs1(x.fi, u);
        subt[u] += subt[x.fi];
    }
}

ll cc;
ll tin[N];
ll tout[N];
ll las;
ll sz;

void dfs2(ll u, ll par){
    tin[u] = cc++;
    ll ni, nj;
    for(auto x : T[u]){
        if(ban[x.fi] || x.fi == par) continue;
        dfs2(x.fi, u);
    }
    tout[u] = cc - 1;
}

void dfs3(ll u, ll par, ll l1, ll r1){
    ll ni, nj;
    for(auto x : T[u]){
        if(ban[x.fi] || x.fi == par) continue;
        ni = l1, nj = r1;
        if(ni == -1)
            ni = tin[x.fi], nj = tout[x.fi];
        dfs3(x.fi, u, ni, nj);
        shi[las].upd(1, 0, sz - 1, tin[x.fi], tout[x.fi], +ww[x.se]);
        G[x.se].push_back({las, tin[x.fi], tout[x.fi], ni, nj});
        if(par == -1){
            shi[las].best.insert(mp(shi[las].get(1, 0, sz - 1, tin[x.fi], tout[x.fi]), tin[x.fi]));
        }
    }
}

void decomp(ll node){
    dfs1(node, -1);
    ll pr = -1;
    bool ok = true;
    sz = subt[node];
    if(sz == 1)
        return;
    while(ok){
        ok = false;
        for(auto x : T[node]){
            if(ban[x.fi] || x.fi == pr) continue;
            if(subt[x.fi] > sz/2){
                pr = node;
                node = x.fi;
                ok = true;
                break;
            }
        }
    }
    shi[idccc].init(sz);
    las=idccc;
    idccc ++ ;
    cc = 0;
    dfs2(node, -1);
    dfs3(node, -1, -1, -1);
    shi[las].check(1);
    ban[node]=true;
    for(auto p : T[node]){
        if(ban[p.fi]) continue;
        decomp(p.fi);
    }
}

int main(){
    fastIO;
    ll lim;
    ll n, q;
    cin >> n >> q >> lim;
    ll u, v;
    for(ll i = 0 ; i < n - 1; i ++ ){
        cin >> u >> v >> ww[i];
        T[u].push_back(mp(v, i));
        T[v].push_back(mp(u, i));
    }
    decomp(1);
    ll lasres = 0;
    ll id;
    ll new_w;
    for(ll tt = 0; tt < q; tt ++ ){
        cin >> id >> new_w;
        id += lasres;
        new_w += lasres;
        id %= (n - 1);
        new_w %= lim;
        lasres = 0;
        for(auto y : G[id]){
            shi[y.id].check(0);
            shi[y.id].best.erase(mp(shi[y.id].get(1, 0, shi[y.id].CURN - 1, y.el, y.er), y.el));
            shi[y.id].upd(1, 0, shi[y.id].CURN - 1, y.op_l, y.op_r, new_w - ww[id]);
            shi[y.id].best.insert(mp(shi[y.id].get(1, 0, shi[y.id].CURN - 1, y.el, y.er), y.el));
            shi[y.id].check(1);
        }
        ww[id] = new_w;
        auto gt = all_di.end();
        gt -- ;
        lasres = *gt;
        cout << lasres << "\n";
    }
    return 0;
}

Compilation message

diameter.cpp: In function 'void dfs2(ll, ll)':
diameter.cpp:122:8: warning: unused variable 'ni' [-Wunused-variable]
     ll ni, nj;
        ^~
diameter.cpp:122:12: warning: unused variable 'nj' [-Wunused-variable]
     ll ni, nj;
            ^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 787824 KB Output is correct
2 Correct 432 ms 787832 KB Output is correct
3 Correct 437 ms 787828 KB Output is correct
4 Correct 431 ms 787928 KB Output is correct
5 Correct 436 ms 787860 KB Output is correct
6 Correct 445 ms 787984 KB Output is correct
7 Correct 480 ms 787960 KB Output is correct
8 Correct 509 ms 787832 KB Output is correct
9 Correct 449 ms 787960 KB Output is correct
10 Correct 431 ms 787832 KB Output is correct
11 Correct 439 ms 787832 KB Output is correct
12 Correct 433 ms 787876 KB Output is correct
13 Correct 451 ms 787960 KB Output is correct
14 Correct 447 ms 787960 KB Output is correct
15 Correct 435 ms 787960 KB Output is correct
16 Correct 456 ms 787960 KB Output is correct
17 Correct 436 ms 788036 KB Output is correct
18 Correct 486 ms 788016 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 787824 KB Output is correct
2 Correct 432 ms 787832 KB Output is correct
3 Correct 437 ms 787828 KB Output is correct
4 Correct 431 ms 787928 KB Output is correct
5 Correct 436 ms 787860 KB Output is correct
6 Correct 445 ms 787984 KB Output is correct
7 Correct 480 ms 787960 KB Output is correct
8 Correct 509 ms 787832 KB Output is correct
9 Correct 449 ms 787960 KB Output is correct
10 Correct 431 ms 787832 KB Output is correct
11 Correct 439 ms 787832 KB Output is correct
12 Correct 433 ms 787876 KB Output is correct
13 Correct 451 ms 787960 KB Output is correct
14 Correct 447 ms 787960 KB Output is correct
15 Correct 435 ms 787960 KB Output is correct
16 Correct 456 ms 787960 KB Output is correct
17 Correct 436 ms 788036 KB Output is correct
18 Correct 486 ms 788016 KB Output is correct
19 Incorrect 459 ms 788896 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 787760 KB Output is correct
2 Correct 462 ms 787960 KB Output is correct
3 Correct 455 ms 787960 KB Output is correct
4 Correct 521 ms 787960 KB Output is correct
5 Correct 508 ms 788344 KB Output is correct
6 Correct 475 ms 787832 KB Output is correct
7 Correct 433 ms 788024 KB Output is correct
8 Correct 433 ms 787968 KB Output is correct
9 Correct 444 ms 788216 KB Output is correct
10 Correct 453 ms 788088 KB Output is correct
11 Correct 595 ms 788528 KB Output is correct
12 Correct 447 ms 789120 KB Output is correct
13 Correct 448 ms 789232 KB Output is correct
14 Correct 510 ms 789104 KB Output is correct
15 Correct 480 ms 789364 KB Output is correct
16 Correct 592 ms 789616 KB Output is correct
17 Correct 638 ms 812880 KB Output is correct
18 Correct 625 ms 812956 KB Output is correct
19 Correct 691 ms 813008 KB Output is correct
20 Correct 697 ms 813008 KB Output is correct
21 Correct 980 ms 813492 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 789168 KB Output is correct
2 Incorrect 500 ms 789240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4119 ms 957492 KB Output is correct
2 Correct 3926 ms 961820 KB Output is correct
3 Correct 3945 ms 960680 KB Output is correct
4 Correct 3832 ms 960400 KB Output is correct
5 Correct 3883 ms 949076 KB Output is correct
6 Correct 3512 ms 889752 KB Output is correct
7 Execution timed out 5125 ms 995736 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 787824 KB Output is correct
2 Correct 432 ms 787832 KB Output is correct
3 Correct 437 ms 787828 KB Output is correct
4 Correct 431 ms 787928 KB Output is correct
5 Correct 436 ms 787860 KB Output is correct
6 Correct 445 ms 787984 KB Output is correct
7 Correct 480 ms 787960 KB Output is correct
8 Correct 509 ms 787832 KB Output is correct
9 Correct 449 ms 787960 KB Output is correct
10 Correct 431 ms 787832 KB Output is correct
11 Correct 439 ms 787832 KB Output is correct
12 Correct 433 ms 787876 KB Output is correct
13 Correct 451 ms 787960 KB Output is correct
14 Correct 447 ms 787960 KB Output is correct
15 Correct 435 ms 787960 KB Output is correct
16 Correct 456 ms 787960 KB Output is correct
17 Correct 436 ms 788036 KB Output is correct
18 Correct 486 ms 788016 KB Output is correct
19 Incorrect 459 ms 788896 KB Output isn't correct
20 Halted 0 ms 0 KB -