oj.uz

Submission #259982

# Submission time Handle Problem Language Result Execution time Memory
259982 2020-08-08T21:32:48 Z doowey Dynamic Diameter (CEOI19_diameter) C++14
73 / 100
 5000 ms 354088 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, 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 + 2;
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)2e6;

struct Node{
    ll val;
    ll lazy;
};

set<pair<ll,int>> all_di;

struct Centroid{
    set<pair<ll,int>> best;
    vector<Node> Tree;
    int CURN;
    int thi_id;
    void init(int n){
        CURN = n;
        for(int i = 0 ; i <= n * 4 + 8; 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(mp(sum,thi_id));
        }
        else{
            all_di.erase(mp(sum,thi_id));
        }
    }
};

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]), ni));
        }
    }
}

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);
    shi[idccc].thi_id = idccc;
    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->fi;
        cout << lasres << "\n";
    }
    return 0;
}

Compilation message

diameter.cpp: In function 'void dfs2(int, int)':
diameter.cpp:123:9: warning: unused variable 'ni' [-Wunused-variable]
     int ni, nj;
         ^~
diameter.cpp:123:13: warning: unused variable 'nj' [-Wunused-variable]
     int ni, nj;
             ^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 161656 KB Output is correct
2 Correct 100 ms 161656 KB Output is correct
3 Correct 100 ms 161656 KB Output is correct
4 Correct 100 ms 161656 KB Output is correct
5 Correct 100 ms 161656 KB Output is correct
6 Correct 100 ms 161656 KB Output is correct
7 Correct 101 ms 161656 KB Output is correct
8 Correct 102 ms 161656 KB Output is correct
9 Correct 100 ms 161800 KB Output is correct
10 Correct 99 ms 161656 KB Output is correct
11 Correct 99 ms 161656 KB Output is correct
12 Correct 100 ms 161656 KB Output is correct
13 Correct 101 ms 161656 KB Output is correct
14 Correct 100 ms 161656 KB Output is correct
15 Correct 101 ms 161656 KB Output is correct
16 Correct 101 ms 161656 KB Output is correct
17 Correct 108 ms 161656 KB Output is correct
18 Correct 112 ms 161660 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 161656 KB Output is correct
2 Correct 100 ms 161656 KB Output is correct
3 Correct 100 ms 161656 KB Output is correct
4 Correct 100 ms 161656 KB Output is correct
5 Correct 100 ms 161656 KB Output is correct
6 Correct 100 ms 161656 KB Output is correct
7 Correct 101 ms 161656 KB Output is correct
8 Correct 102 ms 161656 KB Output is correct
9 Correct 100 ms 161800 KB Output is correct
10 Correct 99 ms 161656 KB Output is correct
11 Correct 99 ms 161656 KB Output is correct
12 Correct 100 ms 161656 KB Output is correct
13 Correct 101 ms 161656 KB Output is correct
14 Correct 100 ms 161656 KB Output is correct
15 Correct 101 ms 161656 KB Output is correct
16 Correct 101 ms 161656 KB Output is correct
17 Correct 108 ms 161656 KB Output is correct
18 Correct 112 ms 161660 KB Output is correct
19 Correct 125 ms 162552 KB Output is correct
20 Correct 134 ms 162552 KB Output is correct
21 Correct 137 ms 162608 KB Output is correct
22 Correct 145 ms 163064 KB Output is correct
23 Correct 156 ms 166384 KB Output is correct
24 Correct 169 ms 167536 KB Output is correct
25 Correct 182 ms 168684 KB Output is correct
26 Correct 177 ms 169972 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 161608 KB Output is correct
2 Correct 99 ms 161664 KB Output is correct
3 Correct 100 ms 161656 KB Output is correct
4 Correct 115 ms 161784 KB Output is correct
5 Correct 178 ms 162040 KB Output is correct
6 Correct 100 ms 161656 KB Output is correct
7 Correct 100 ms 161656 KB Output is correct
8 Correct 100 ms 161776 KB Output is correct
9 Correct 105 ms 161784 KB Output is correct
10 Correct 123 ms 161784 KB Output is correct
11 Correct 223 ms 162168 KB Output is correct
12 Correct 106 ms 162800 KB Output is correct
13 Correct 115 ms 162672 KB Output is correct
14 Correct 116 ms 162672 KB Output is correct
15 Correct 143 ms 162800 KB Output is correct
16 Correct 253 ms 163184 KB Output is correct
17 Correct 282 ms 183116 KB Output is correct
18 Correct 287 ms 183252 KB Output is correct
19 Correct 303 ms 183116 KB Output is correct
20 Correct 354 ms 183244 KB Output is correct
21 Correct 650 ms 183756 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 162808 KB Output is correct
2 Correct 157 ms 162936 KB Output is correct
3 Correct 305 ms 163064 KB Output is correct
4 Correct 487 ms 163576 KB Output is correct
5 Correct 166 ms 177648 KB Output is correct
6 Correct 221 ms 177776 KB Output is correct
7 Correct 495 ms 178160 KB Output is correct
8 Correct 831 ms 178288 KB Output is correct
9 Correct 448 ms 253408 KB Output is correct
10 Correct 546 ms 253536 KB Output is correct
11 Correct 991 ms 254072 KB Output is correct
12 Correct 1557 ms 254140 KB Output is correct
13 Correct 859 ms 353488 KB Output is correct
14 Correct 1061 ms 353444 KB Output is correct
15 Correct 1580 ms 353820 KB Output is correct
16 Correct 2267 ms 354088 KB Output is correct
17 Correct 3863 ms 354068 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3576 ms 300112 KB Output is correct
2 Correct 3554 ms 303184 KB Output is correct
3 Correct 3624 ms 301972 KB Output is correct
4 Correct 3594 ms 302476 KB Output is correct
5 Correct 3470 ms 293136 KB Output is correct
6 Correct 3011 ms 245464 KB Output is correct
7 Correct 4456 ms 332880 KB Output is correct
8 Correct 4682 ms 333140 KB Output is correct
9 Correct 4608 ms 337236 KB Output is correct
10 Correct 4642 ms 336336 KB Output is correct
11 Correct 4380 ms 324888 KB Output is correct
12 Correct 3947 ms 266848 KB Output is correct
13 Correct 4492 ms 353040 KB Output is correct
14 Correct 4323 ms 353088 KB Output is correct
15 Correct 4383 ms 353140 KB Output is correct
16 Correct 4555 ms 352208 KB Output is correct
17 Correct 4422 ms 340036 KB Output is correct
18 Correct 3604 ms 274900 KB Output is correct
19 Correct 4541 ms 352976 KB Output is correct
20 Correct 4638 ms 353276 KB Output is correct
21 Correct 4437 ms 353080 KB Output is correct
22 Correct 4503 ms 352276 KB Output is correct
23 Correct 4497 ms 340076 KB Output is correct
24 Correct 3646 ms 274872 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 161656 KB Output is correct
2 Correct 100 ms 161656 KB Output is correct
3 Correct 100 ms 161656 KB Output is correct
4 Correct 100 ms 161656 KB Output is correct
5 Correct 100 ms 161656 KB Output is correct
6 Correct 100 ms 161656 KB Output is correct
7 Correct 101 ms 161656 KB Output is correct
8 Correct 102 ms 161656 KB Output is correct
9 Correct 100 ms 161800 KB Output is correct
10 Correct 99 ms 161656 KB Output is correct
11 Correct 99 ms 161656 KB Output is correct
12 Correct 100 ms 161656 KB Output is correct
13 Correct 101 ms 161656 KB Output is correct
14 Correct 100 ms 161656 KB Output is correct
15 Correct 101 ms 161656 KB Output is correct
16 Correct 101 ms 161656 KB Output is correct
17 Correct 108 ms 161656 KB Output is correct
18 Correct 112 ms 161660 KB Output is correct
19 Correct 125 ms 162552 KB Output is correct
20 Correct 134 ms 162552 KB Output is correct
21 Correct 137 ms 162608 KB Output is correct
22 Correct 145 ms 163064 KB Output is correct
23 Correct 156 ms 166384 KB Output is correct
24 Correct 169 ms 167536 KB Output is correct
25 Correct 182 ms 168684 KB Output is correct
26 Correct 177 ms 169972 KB Output is correct
27 Correct 99 ms 161608 KB Output is correct
28 Correct 99 ms 161664 KB Output is correct
29 Correct 100 ms 161656 KB Output is correct
30 Correct 115 ms 161784 KB Output is correct
31 Correct 178 ms 162040 KB Output is correct
32 Correct 100 ms 161656 KB Output is correct
33 Correct 100 ms 161656 KB Output is correct
34 Correct 100 ms 161776 KB Output is correct
35 Correct 105 ms 161784 KB Output is correct
36 Correct 123 ms 161784 KB Output is correct
37 Correct 223 ms 162168 KB Output is correct
38 Correct 106 ms 162800 KB Output is correct
39 Correct 115 ms 162672 KB Output is correct
40 Correct 116 ms 162672 KB Output is correct
41 Correct 143 ms 162800 KB Output is correct
42 Correct 253 ms 163184 KB Output is correct
43 Correct 282 ms 183116 KB Output is correct
44 Correct 287 ms 183252 KB Output is correct
45 Correct 303 ms 183116 KB Output is correct
46 Correct 354 ms 183244 KB Output is correct
47 Correct 650 ms 183756 KB Output is correct
48 Correct 107 ms 162808 KB Output is correct
49 Correct 157 ms 162936 KB Output is correct
50 Correct 305 ms 163064 KB Output is correct
51 Correct 487 ms 163576 KB Output is correct
52 Correct 166 ms 177648 KB Output is correct
53 Correct 221 ms 177776 KB Output is correct
54 Correct 495 ms 178160 KB Output is correct
55 Correct 831 ms 178288 KB Output is correct
56 Correct 448 ms 253408 KB Output is correct
57 Correct 546 ms 253536 KB Output is correct
58 Correct 991 ms 254072 KB Output is correct
59 Correct 1557 ms 254140 KB Output is correct
60 Correct 859 ms 353488 KB Output is correct
61 Correct 1061 ms 353444 KB Output is correct
62 Correct 1580 ms 353820 KB Output is correct
63 Correct 2267 ms 354088 KB Output is correct
64 Correct 3863 ms 354068 KB Output is correct
65 Correct 3576 ms 300112 KB Output is correct
66 Correct 3554 ms 303184 KB Output is correct
67 Correct 3624 ms 301972 KB Output is correct
68 Correct 3594 ms 302476 KB Output is correct
69 Correct 3470 ms 293136 KB Output is correct
70 Correct 3011 ms 245464 KB Output is correct
71 Correct 4456 ms 332880 KB Output is correct
72 Correct 4682 ms 333140 KB Output is correct
73 Correct 4608 ms 337236 KB Output is correct
74 Correct 4642 ms 336336 KB Output is correct
75 Correct 4380 ms 324888 KB Output is correct
76 Correct 3947 ms 266848 KB Output is correct
77 Correct 4492 ms 353040 KB Output is correct
78 Correct 4323 ms 353088 KB Output is correct
79 Correct 4383 ms 353140 KB Output is correct
80 Correct 4555 ms 352208 KB Output is correct
81 Correct 4422 ms 340036 KB Output is correct
82 Correct 3604 ms 274900 KB Output is correct
83 Correct 4541 ms 352976 KB Output is correct
84 Correct 4638 ms 353276 KB Output is correct
85 Correct 4437 ms 353080 KB Output is correct
86 Correct 4503 ms 352276 KB Output is correct
87 Correct 4497 ms 340076 KB Output is correct
88 Correct 3646 ms 274872 KB Output is correct
89 Correct 3574 ms 303844 KB Output is correct
90 Correct 4170 ms 315888 KB Output is correct
91 Correct 4749 ms 332048 KB Output is correct
92 Execution timed out 5043 ms 336084 KB Time limit exceeded
93 Halted 0 ms 0 KB -