oj.uz

Submission #259968

# Submission time Handle Problem Language Result Execution time Memory
259968 2020-08-08T21:18:49 Z doowey Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 5000 ms 981000 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> 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 int N = (int)1e5 + 5;
ll ww[N];
vector<pii> T[N];

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

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

struct Node{
    ll val;
    ll lazy;
};

multiset<ll> all_di;

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

Centroid shi[M];
int idccc = 0;

bool ban[N];
int subt[N];

void dfs1(int u, int 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];
    }
}

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

void dfs2(int u, int par){
    tin[u] = cc++;
    int 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(int u, int par, int l1, int r1){
    int 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(int node){
    dfs1(node, -1);
    int 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;
    int n, q;
    cin >> n >> q >> lim;
    int u, v;
    for(int 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(int 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(int, int)':
diameter.cpp:122:9: warning: unused variable 'ni' [-Wunused-variable]
     int ni, nj;
         ^~
diameter.cpp:122:13: warning: unused variable 'nj' [-Wunused-variable]
     int ni, nj;
             ^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 787832 KB Output is correct
2 Correct 455 ms 787832 KB Output is correct
3 Correct 460 ms 787832 KB Output is correct
4 Correct 453 ms 787832 KB Output is correct
5 Correct 455 ms 787908 KB Output is correct
6 Correct 462 ms 787832 KB Output is correct
7 Correct 453 ms 787832 KB Output is correct
8 Correct 455 ms 787832 KB Output is correct
9 Correct 454 ms 787960 KB Output is correct
10 Correct 455 ms 787960 KB Output is correct
11 Correct 459 ms 787832 KB Output is correct
12 Correct 452 ms 787832 KB Output is correct
13 Correct 458 ms 787960 KB Output is correct
14 Correct 454 ms 787960 KB Output is correct
15 Correct 457 ms 788012 KB Output is correct
16 Correct 454 ms 787832 KB Output is correct
17 Correct 455 ms 787832 KB Output is correct
18 Correct 456 ms 787960 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 787832 KB Output is correct
2 Correct 455 ms 787832 KB Output is correct
3 Correct 460 ms 787832 KB Output is correct
4 Correct 453 ms 787832 KB Output is correct
5 Correct 455 ms 787908 KB Output is correct
6 Correct 462 ms 787832 KB Output is correct
7 Correct 453 ms 787832 KB Output is correct
8 Correct 455 ms 787832 KB Output is correct
9 Correct 454 ms 787960 KB Output is correct
10 Correct 455 ms 787960 KB Output is correct
11 Correct 459 ms 787832 KB Output is correct
12 Correct 452 ms 787832 KB Output is correct
13 Correct 458 ms 787960 KB Output is correct
14 Correct 454 ms 787960 KB Output is correct
15 Correct 457 ms 788012 KB Output is correct
16 Correct 454 ms 787832 KB Output is correct
17 Correct 455 ms 787832 KB Output is correct
18 Correct 456 ms 787960 KB Output is correct
19 Correct 482 ms 788856 KB Output is correct
20 Correct 481 ms 788988 KB Output is correct
21 Correct 492 ms 789112 KB Output is correct
22 Correct 491 ms 789496 KB Output is correct
23 Correct 527 ms 792812 KB Output is correct
24 Correct 548 ms 793948 KB Output is correct
25 Correct 544 ms 794996 KB Output is correct
26 Correct 535 ms 796276 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 787832 KB Output is correct
2 Correct 478 ms 787816 KB Output is correct
3 Correct 467 ms 787868 KB Output is correct
4 Correct 472 ms 788088 KB Output is correct
5 Correct 551 ms 789020 KB Output is correct
6 Correct 455 ms 787776 KB Output is correct
7 Correct 471 ms 787964 KB Output is correct
8 Correct 457 ms 787960 KB Output is correct
9 Correct 473 ms 787992 KB Output is correct
10 Correct 491 ms 788344 KB Output is correct
11 Correct 568 ms 789280 KB Output is correct
12 Correct 461 ms 788976 KB Output is correct
13 Correct 466 ms 789104 KB Output is correct
14 Correct 468 ms 789104 KB Output is correct
15 Correct 495 ms 789360 KB Output is correct
16 Correct 630 ms 790768 KB Output is correct
17 Correct 715 ms 811472 KB Output is correct
18 Correct 650 ms 811344 KB Output is correct
19 Correct 680 ms 811344 KB Output is correct
20 Correct 733 ms 811728 KB Output is correct
21 Correct 981 ms 813156 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 789112 KB Output is correct
2 Correct 506 ms 789240 KB Output is correct
3 Correct 663 ms 789752 KB Output is correct
4 Correct 826 ms 790648 KB Output is correct
5 Correct 523 ms 804208 KB Output is correct
6 Correct 598 ms 804332 KB Output is correct
7 Correct 870 ms 804976 KB Output is correct
8 Correct 1279 ms 805856 KB Output is correct
9 Correct 806 ms 880464 KB Output is correct
10 Correct 920 ms 880732 KB Output is correct
11 Correct 1399 ms 881372 KB Output is correct
12 Correct 1955 ms 882268 KB Output is correct
13 Correct 1302 ms 979536 KB Output is correct
14 Correct 1379 ms 979764 KB Output is correct
15 Correct 1934 ms 980292 KB Output is correct
16 Correct 2899 ms 981000 KB Output is correct
17 Execution timed out 5143 ms 980792 KB Time limit exceeded

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4437 ms 932948 KB Output is correct
2 Correct 4690 ms 936248 KB Output is correct
3 Correct 4112 ms 935392 KB Output is correct
4 Correct 3969 ms 935576 KB Output is correct
5 Correct 4180 ms 925996 KB Output is correct
6 Correct 3412 ms 877492 KB Output is correct
7 Correct 4987 ms 966868 KB Output is correct
8 Execution timed out 5089 ms 967348 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 787832 KB Output is correct
2 Correct 455 ms 787832 KB Output is correct
3 Correct 460 ms 787832 KB Output is correct
4 Correct 453 ms 787832 KB Output is correct
5 Correct 455 ms 787908 KB Output is correct
6 Correct 462 ms 787832 KB Output is correct
7 Correct 453 ms 787832 KB Output is correct
8 Correct 455 ms 787832 KB Output is correct
9 Correct 454 ms 787960 KB Output is correct
10 Correct 455 ms 787960 KB Output is correct
11 Correct 459 ms 787832 KB Output is correct
12 Correct 452 ms 787832 KB Output is correct
13 Correct 458 ms 787960 KB Output is correct
14 Correct 454 ms 787960 KB Output is correct
15 Correct 457 ms 788012 KB Output is correct
16 Correct 454 ms 787832 KB Output is correct
17 Correct 455 ms 787832 KB Output is correct
18 Correct 456 ms 787960 KB Output is correct
19 Correct 482 ms 788856 KB Output is correct
20 Correct 481 ms 788988 KB Output is correct
21 Correct 492 ms 789112 KB Output is correct
22 Correct 491 ms 789496 KB Output is correct
23 Correct 527 ms 792812 KB Output is correct
24 Correct 548 ms 793948 KB Output is correct
25 Correct 544 ms 794996 KB Output is correct
26 Correct 535 ms 796276 KB Output is correct
27 Correct 458 ms 787832 KB Output is correct
28 Correct 478 ms 787816 KB Output is correct
29 Correct 467 ms 787868 KB Output is correct
30 Correct 472 ms 788088 KB Output is correct
31 Correct 551 ms 789020 KB Output is correct
32 Correct 455 ms 787776 KB Output is correct
33 Correct 471 ms 787964 KB Output is correct
34 Correct 457 ms 787960 KB Output is correct
35 Correct 473 ms 787992 KB Output is correct
36 Correct 491 ms 788344 KB Output is correct
37 Correct 568 ms 789280 KB Output is correct
38 Correct 461 ms 788976 KB Output is correct
39 Correct 466 ms 789104 KB Output is correct
40 Correct 468 ms 789104 KB Output is correct
41 Correct 495 ms 789360 KB Output is correct
42 Correct 630 ms 790768 KB Output is correct
43 Correct 715 ms 811472 KB Output is correct
44 Correct 650 ms 811344 KB Output is correct
45 Correct 680 ms 811344 KB Output is correct
46 Correct 733 ms 811728 KB Output is correct
47 Correct 981 ms 813156 KB Output is correct
48 Correct 474 ms 789112 KB Output is correct
49 Correct 506 ms 789240 KB Output is correct
50 Correct 663 ms 789752 KB Output is correct
51 Correct 826 ms 790648 KB Output is correct
52 Correct 523 ms 804208 KB Output is correct
53 Correct 598 ms 804332 KB Output is correct
54 Correct 870 ms 804976 KB Output is correct
55 Correct 1279 ms 805856 KB Output is correct
56 Correct 806 ms 880464 KB Output is correct
57 Correct 920 ms 880732 KB Output is correct
58 Correct 1399 ms 881372 KB Output is correct
59 Correct 1955 ms 882268 KB Output is correct
60 Correct 1302 ms 979536 KB Output is correct
61 Correct 1379 ms 979764 KB Output is correct
62 Correct 1934 ms 980292 KB Output is correct
63 Correct 2899 ms 981000 KB Output is correct
64 Execution timed out 5143 ms 980792 KB Time limit exceeded