oj.uz

Submission #259937

# Submission time Handle Problem Language Result Execution time Memory
259937 2020-08-08T20:31:50 Z doowey Dynamic Diameter (CEOI19_diameter) C++14
18 / 100
 1333 ms 1048576 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 + 60; 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(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];
    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 437 ms 787852 KB Output is correct
2 Correct 432 ms 787832 KB Output is correct
3 Correct 436 ms 787832 KB Output is correct
4 Correct 438 ms 787832 KB Output is correct
5 Correct 435 ms 787832 KB Output is correct
6 Correct 441 ms 787960 KB Output is correct
7 Correct 435 ms 787960 KB Output is correct
8 Correct 436 ms 787960 KB Output is correct
9 Correct 443 ms 787960 KB Output is correct
10 Correct 437 ms 787960 KB Output is correct
11 Correct 429 ms 787904 KB Output is correct
12 Correct 441 ms 787960 KB Output is correct
13 Correct 437 ms 788112 KB Output is correct
14 Correct 439 ms 788088 KB Output is correct
15 Correct 434 ms 788088 KB Output is correct
16 Correct 437 ms 788088 KB Output is correct
17 Correct 436 ms 788088 KB Output is correct
18 Correct 434 ms 788216 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 787852 KB Output is correct
2 Correct 432 ms 787832 KB Output is correct
3 Correct 436 ms 787832 KB Output is correct
4 Correct 438 ms 787832 KB Output is correct
5 Correct 435 ms 787832 KB Output is correct
6 Correct 441 ms 787960 KB Output is correct
7 Correct 435 ms 787960 KB Output is correct
8 Correct 436 ms 787960 KB Output is correct
9 Correct 443 ms 787960 KB Output is correct
10 Correct 437 ms 787960 KB Output is correct
11 Correct 429 ms 787904 KB Output is correct
12 Correct 441 ms 787960 KB Output is correct
13 Correct 437 ms 788112 KB Output is correct
14 Correct 439 ms 788088 KB Output is correct
15 Correct 434 ms 788088 KB Output is correct
16 Correct 437 ms 788088 KB Output is correct
17 Correct 436 ms 788088 KB Output is correct
18 Correct 434 ms 788216 KB Output is correct
19 Incorrect 458 ms 790392 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 437 ms 787832 KB Output is correct
2 Correct 430 ms 787832 KB Output is correct
3 Correct 436 ms 787836 KB Output is correct
4 Correct 446 ms 788344 KB Output is correct
5 Correct 513 ms 788344 KB Output is correct
6 Correct 438 ms 787832 KB Output is correct
7 Correct 429 ms 788984 KB Output is correct
8 Correct 438 ms 789020 KB Output is correct
9 Correct 437 ms 789024 KB Output is correct
10 Correct 464 ms 789112 KB Output is correct
11 Correct 552 ms 789496 KB Output is correct
12 Correct 455 ms 799344 KB Output is correct
13 Correct 455 ms 799344 KB Output is correct
14 Correct 462 ms 799344 KB Output is correct
15 Correct 485 ms 799344 KB Output is correct
16 Correct 639 ms 799984 KB Output is correct
17 Correct 911 ms 1016888 KB Output is correct
18 Correct 882 ms 1016884 KB Output is correct
19 Correct 883 ms 1017040 KB Output is correct
20 Correct 1004 ms 1017040 KB Output is correct
21 Correct 1333 ms 1017552 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 790520 KB Output is correct
2 Incorrect 488 ms 790648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1308 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 787852 KB Output is correct
2 Correct 432 ms 787832 KB Output is correct
3 Correct 436 ms 787832 KB Output is correct
4 Correct 438 ms 787832 KB Output is correct
5 Correct 435 ms 787832 KB Output is correct
6 Correct 441 ms 787960 KB Output is correct
7 Correct 435 ms 787960 KB Output is correct
8 Correct 436 ms 787960 KB Output is correct
9 Correct 443 ms 787960 KB Output is correct
10 Correct 437 ms 787960 KB Output is correct
11 Correct 429 ms 787904 KB Output is correct
12 Correct 441 ms 787960 KB Output is correct
13 Correct 437 ms 788112 KB Output is correct
14 Correct 439 ms 788088 KB Output is correct
15 Correct 434 ms 788088 KB Output is correct
16 Correct 437 ms 788088 KB Output is correct
17 Correct 436 ms 788088 KB Output is correct
18 Correct 434 ms 788216 KB Output is correct
19 Incorrect 458 ms 790392 KB Output isn't correct
20 Halted 0 ms 0 KB -