oj.uz

Submission #259936

# Submission time Handle Problem Language Result Execution time Memory
259936 2020-08-08T20:30:42 Z doowey Dynamic Diameter (CEOI19_diameter) C++14
11 / 100
 1591 ms 1048580 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)2e6;

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 + 512; 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 93 ms 161916 KB Output is correct
2 Correct 91 ms 161788 KB Output is correct
3 Correct 92 ms 161784 KB Output is correct
4 Correct 91 ms 161704 KB Output is correct
5 Correct 92 ms 161784 KB Output is correct
6 Correct 93 ms 161784 KB Output is correct
7 Correct 94 ms 162168 KB Output is correct
8 Correct 93 ms 162168 KB Output is correct
9 Correct 93 ms 162172 KB Output is correct
10 Correct 92 ms 162296 KB Output is correct
11 Correct 95 ms 162296 KB Output is correct
12 Correct 97 ms 162172 KB Output is correct
13 Correct 95 ms 163064 KB Output is correct
14 Correct 104 ms 162936 KB Output is correct
15 Correct 94 ms 162936 KB Output is correct
16 Correct 96 ms 162936 KB Output is correct
17 Correct 94 ms 162936 KB Output is correct
18 Correct 95 ms 162808 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 161916 KB Output is correct
2 Correct 91 ms 161788 KB Output is correct
3 Correct 92 ms 161784 KB Output is correct
4 Correct 91 ms 161704 KB Output is correct
5 Correct 92 ms 161784 KB Output is correct
6 Correct 93 ms 161784 KB Output is correct
7 Correct 94 ms 162168 KB Output is correct
8 Correct 93 ms 162168 KB Output is correct
9 Correct 93 ms 162172 KB Output is correct
10 Correct 92 ms 162296 KB Output is correct
11 Correct 95 ms 162296 KB Output is correct
12 Correct 97 ms 162172 KB Output is correct
13 Correct 95 ms 163064 KB Output is correct
14 Correct 104 ms 162936 KB Output is correct
15 Correct 94 ms 162936 KB Output is correct
16 Correct 96 ms 162936 KB Output is correct
17 Correct 94 ms 162936 KB Output is correct
18 Correct 95 ms 162808 KB Output is correct
19 Incorrect 135 ms 174456 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 161912 KB Output is correct
2 Correct 92 ms 161912 KB Output is correct
3 Correct 101 ms 161936 KB Output is correct
4 Correct 107 ms 161912 KB Output is correct
5 Correct 172 ms 162296 KB Output is correct
6 Correct 91 ms 161656 KB Output is correct
7 Correct 99 ms 168696 KB Output is correct
8 Correct 99 ms 168696 KB Output is correct
9 Correct 104 ms 168696 KB Output is correct
10 Correct 137 ms 168824 KB Output is correct
11 Correct 222 ms 169208 KB Output is correct
12 Correct 171 ms 233584 KB Output is correct
13 Correct 169 ms 233584 KB Output is correct
14 Correct 188 ms 233716 KB Output is correct
15 Correct 221 ms 233712 KB Output is correct
16 Correct 335 ms 234100 KB Output is correct
17 Runtime error 1074 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 174584 KB Output is correct
2 Incorrect 158 ms 174584 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 1591 ms 1048580 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 93 ms 161916 KB Output is correct
2 Correct 91 ms 161788 KB Output is correct
3 Correct 92 ms 161784 KB Output is correct
4 Correct 91 ms 161704 KB Output is correct
5 Correct 92 ms 161784 KB Output is correct
6 Correct 93 ms 161784 KB Output is correct
7 Correct 94 ms 162168 KB Output is correct
8 Correct 93 ms 162168 KB Output is correct
9 Correct 93 ms 162172 KB Output is correct
10 Correct 92 ms 162296 KB Output is correct
11 Correct 95 ms 162296 KB Output is correct
12 Correct 97 ms 162172 KB Output is correct
13 Correct 95 ms 163064 KB Output is correct
14 Correct 104 ms 162936 KB Output is correct
15 Correct 94 ms 162936 KB Output is correct
16 Correct 96 ms 162936 KB Output is correct
17 Correct 94 ms 162936 KB Output is correct
18 Correct 95 ms 162808 KB Output is correct
19 Incorrect 135 ms 174456 KB Output isn't correct
20 Halted 0 ms 0 KB -