oj.uz

Submission #971985

# Submission time Handle Problem Language Result Execution time Memory
971985 2024-04-29T16:14:30 Z efedmrlr Dynamic Diameter (CEOI19_diameter) C++17
49 / 100
 3471 ms 214848 KB 
#include <bits/stdc++.h>
#define lli long long int
#define pb push_back
#define MP make_pair
#define ld long double
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 1e5 + 5;
const int INF = 1e9 + 500;
const int LGN = 18;

struct SegT {
    vector<lli> st, tag;
    int n;
    void build(int tl, int tr, int v, vector<lli> &x) {
        if(tl == tr) {
            st[v] = x[tl];
            return;
        }
        int tm = (tl + tr) >> 1;
        build(tl, tm, v << 1, x);
        build(tm + 1, tr, v << 1 ^ 1, x);
        st[v] = max(st[v << 1], st[v << 1 ^ 1]);
    }
    void reset(int nn) {
        n = nn;
        st.assign(4*(n + 3), 0);
        tag.assign(4*(n + 3), 0);
    }
    void push(int v) {
        st[v << 1] += tag[v];
        st[v << 1 ^ 1] += tag[v];

        tag[v << 1] += tag[v];
        tag[v << 1 ^ 1] += tag[v];
        tag[v] = 0;
    }
    void update(int tl, int tr, int v, int l, int r, int val) {
        if(tl >= l && tr <= r) {
            st[v] += val;
            tag[v] += val;
            return;
        }
        if(tl > r || tr < l) {
            return;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        update(tl, tm, v << 1, l, r, val);
        update(tm + 1, tr, v << 1 ^ 1, l, r, val);
        st[v] = max(st[v << 1], st[v << 1 ^ 1]);
    }
    void update(int l, int r, int val) {
        update(0, n, 1, l, r, val);
    }
    lli query(int tl, int tr, int v, int l, int r) {
        if(tl >= l && tr <= r) {
            return st[v];
        }
        if(tl > r || tr < l) {
            return 0;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        return max(query(tl, tm, v << 1, l, r), query(tm + 1, tr, v << 1 ^ 1, l, r));
    }
    lli query(int l, int r) {
        return query(0, n, 1, l, r);
    }
};
int n = 0, q = 0, w = 0;
vector<vector<array<int, 2> > > adj(N, vector<array<int, 2> >());
vector<array<int, 3> > edg;
vector<int> sub(N, 0);
vector<int> vis(N, 0);
array<SegT, LGN> st;
vector<array<int, LGN> > cent(N);
vector<array<int, LGN> > tin(N), p(N), ssz(N);
vector<array<int, LGN> > comp(N);
vector<array<int, LGN> > edgnode(N);
array<int, LGN> tim;
array<vector<lli>, LGN> arr;
vector<set<array<lli, 2>, greater<array<lli, 2> > > > cand(N, set<array<lli, 2>, greater<array<lli, 2> > >());
vector<vector<array<lli, 2> > > cent_adj(N, vector<array<lli, 2> >());
set<array<lli, 2>, greater<array<lli, 2> > > anss;
vector<int> lv(N, 0);
vector<lli> cent_res(N, 0);
void dfssz(int node, int par) {
    sub[node] = 1;
    for(auto c : adj[node]) {
        if(c[0] == par || vis[c[0]]) {
            continue;
        }
        dfssz(c[0], node);
        sub[node] += sub[c[0]];
    }
}
int get_cent(int node, int par, int tar) {
    for(auto c : adj[node]) {
        if(c[0] == par || vis[c[0]]) continue;
        if(sub[c[0]] * 2 > tar) {
            return get_cent(c[0], node, tar);
        }
    }
    return node;
}
void prec(int node, int par, int lvl, int centro) {
    ssz[node][lvl] = 1;
    tin[node][lvl] = tim[lvl]++;
    cent[node][lvl] = centro;
    for(auto &c : adj[node]) {
        if(c[0] == par || vis[c[0]]) continue;
        p[c[0]][lvl] = node;
        edgnode[c[1]][lvl] = c[0];
        prec(c[0], node, lvl, centro);
        ssz[node][lvl] += ssz[c[0]][lvl];
    }

}
void prec2(int node, int par, int lvl, int g) {
    comp[node][lvl] = g;
    for(auto c : adj[node]) {
        if(c[0] == par || vis[c[0]]) continue;
        prec2(c[0], node, lvl, g);
    }
}
void prec3(int node, int par, int lvl) {

    for(auto c : adj[node]) {
        if(c[0] == par || vis[c[0]]) continue;
        arr[lvl][tin[c[0]][lvl]] = arr[lvl][tin[node][lvl]] + edg[c[1]][2];
        prec3(c[0], node, lvl);
    }
}
void centroid_decomp(int node, int lvl) {
    dfssz(node, 0);
    int centro = get_cent(node, 0, sub[node]);
    lv[centro] = lvl;
    p[centro][lvl] = 0;
    prec(centro, 0, lvl, centro);
    for(auto c : adj[centro]) {
        if(vis[c[0]]) continue;
        cent_adj[centro].pb({c[0], 0});
        prec2(c[0], centro, lvl, c[0]);
    }
    arr[lvl][tin[centro][lvl]] = 0;
    prec3(centro, 0, lvl);
    vis[centro] = 1;
    for(auto c : adj[centro]) {
        if(vis[c[0]]) continue;
        centroid_decomp(c[0], lvl + 1);
    }
}

void solve() {
    REP(i, LGN) {
        tim[i] = 0;
        arr[i].assign(N, 0);
        REP(j, N) edgnode[j][i] = -1;
    }
    cin >> n >> q >> w;
    
    edg.resize(n - 1);
    REP(i, n - 1) {
        cin >> edg[i][0] >> edg[i][1] >> edg[i][2];
        adj[edg[i][0]].pb({edg[i][1], i});
        adj[edg[i][1]].pb({edg[i][0], i});
    }
    centroid_decomp(1, 0);
    REP(i, LGN) {
        st[i].reset(n + 1);
        st[i].build(0, st[i].n, 1, arr[i]);
    }
    for(int i = 1; i <= n; i++) {
        sort(all(cent_adj[i]));
        for(auto &c : cent_adj[i]) {
            lli v = st[lv[i]].query(tin[c[0]][lv[i]], tin[c[0]][lv[i]] + ssz[c[0]][lv[i]] - 1);
            cand[i].insert({v, c[0]});
            c[1] = v;
        }
        cand[i].insert({0, -1});
        cand[i].insert({0, -2});
        cent_res[i] = (*cand[i].begin())[0] + (*next(cand[i].begin()))[0];
        anss.insert({cent_res[i], i});
    }
 
    // for(int i = 1; i <= n; i++) {
    //     cout << "i:" << i << "\n";
    //     for(auto c : cent_adj[i]) {
    //         cout << c[0] << " " << c[1] << "\n";
    //     }
    // }
    lli last = 0;
    REP(z, q) {
        int d, e;
        cin >> d >> e;
        d = (int)((1ll * d + last) % (n - 1));
        e = (int)((1ll * e + last) % w);
        // cout << "d:" << d <<" e:" << e << "\n";
        for(int i = 0; i < LGN; i++) {
            if(edgnode[d][i] == -1) continue;
            // cout << "level:" << i << "\n";
            int node = edgnode[d][i];
            int centr = cent[node][i];
            int rep = comp[node][i];
            auto itr = lower_bound(all(cent_adj[centr]), array<lli, 2>({rep, 0}));
            
            // if(rep != (*itr)[0]) {
            //     itr--;
            //     cerr << (*itr)[0] << "REP" << (*itr)[1] << endl;
            // }
            // cout << "node :" << node << " centr:" << centr << " rep:" << rep << " ";
            cand[centr].erase({(*itr)[1], rep});
            st[i].update(tin[node][i], tin[node][i] + ssz[node][i] - 1, e - edg[d][2]);
            // cout << "old val: " << (*itr)[1] << " ";   
            (*itr)[1] = st[i].query(tin[rep][i], tin[rep][i] + ssz[rep][i] - 1);
            // cout << "new val: " << (*itr)[1] << "\n";
            cand[centr].insert({(*itr)[1], rep});
            
            anss.erase({cent_res[centr], centr});
            cent_res[centr] = (*cand[centr].begin())[0] + (*next(cand[centr].begin()))[0];
            anss.insert({cent_res[centr], centr});
        }
        edg[d][2] = e;
        // cout << "centro:" << (*anss.begin())[1] << " lvl:" << lv[(*anss.begin())[1]] << "\n";
        last = (*anss.begin())[0];
        cout << last << "\n";
    }

}

signed main() {
    fastio();
    solve();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 68180 KB Output is correct
2 Correct 32 ms 68152 KB Output is correct
3 Correct 32 ms 68232 KB Output is correct
4 Correct 32 ms 68184 KB Output is correct
5 Correct 31 ms 68052 KB Output is correct
6 Correct 32 ms 68188 KB Output is correct
7 Correct 36 ms 68184 KB Output is correct
8 Correct 36 ms 68188 KB Output is correct
9 Correct 31 ms 68180 KB Output is correct
10 Correct 40 ms 68072 KB Output is correct
11 Correct 34 ms 68176 KB Output is correct
12 Correct 31 ms 68180 KB Output is correct
13 Correct 39 ms 68180 KB Output is correct
14 Correct 32 ms 68272 KB Output is correct
15 Correct 32 ms 68176 KB Output is correct
16 Correct 32 ms 68188 KB Output is correct
17 Correct 41 ms 68180 KB Output is correct
18 Correct 33 ms 68192 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 68180 KB Output is correct
2 Correct 32 ms 68152 KB Output is correct
3 Correct 32 ms 68232 KB Output is correct
4 Correct 32 ms 68184 KB Output is correct
5 Correct 31 ms 68052 KB Output is correct
6 Correct 32 ms 68188 KB Output is correct
7 Correct 36 ms 68184 KB Output is correct
8 Correct 36 ms 68188 KB Output is correct
9 Correct 31 ms 68180 KB Output is correct
10 Correct 40 ms 68072 KB Output is correct
11 Correct 34 ms 68176 KB Output is correct
12 Correct 31 ms 68180 KB Output is correct
13 Correct 39 ms 68180 KB Output is correct
14 Correct 32 ms 68272 KB Output is correct
15 Correct 32 ms 68176 KB Output is correct
16 Correct 32 ms 68188 KB Output is correct
17 Correct 41 ms 68180 KB Output is correct
18 Correct 33 ms 68192 KB Output is correct
19 Correct 51 ms 69764 KB Output is correct
20 Correct 49 ms 69696 KB Output is correct
21 Correct 48 ms 69716 KB Output is correct
22 Correct 59 ms 69736 KB Output is correct
23 Correct 78 ms 75604 KB Output is correct
24 Correct 76 ms 75600 KB Output is correct
25 Correct 108 ms 75652 KB Output is correct
26 Correct 109 ms 76036 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 68180 KB Output is correct
2 Correct 26 ms 68184 KB Output is correct
3 Correct 29 ms 68304 KB Output is correct
4 Correct 40 ms 68432 KB Output is correct
5 Correct 80 ms 69204 KB Output is correct
6 Correct 29 ms 68200 KB Output is correct
7 Correct 25 ms 68944 KB Output is correct
8 Correct 25 ms 68944 KB Output is correct
9 Correct 32 ms 68956 KB Output is correct
10 Correct 41 ms 69152 KB Output is correct
11 Correct 106 ms 69984 KB Output is correct
12 Correct 37 ms 75600 KB Output is correct
13 Correct 37 ms 75416 KB Output is correct
14 Correct 34 ms 75668 KB Output is correct
15 Correct 54 ms 75860 KB Output is correct
16 Correct 145 ms 76624 KB Output is correct
17 Correct 224 ms 213720 KB Output is correct
18 Correct 204 ms 213568 KB Output is correct
19 Correct 204 ms 213572 KB Output is correct
20 Correct 229 ms 213808 KB Output is correct
21 Correct 478 ms 214848 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 69712 KB Output is correct
2 Correct 56 ms 69716 KB Output is correct
3 Correct 167 ms 70228 KB Output is correct
4 Correct 317 ms 70868 KB Output is correct
5 Correct 51 ms 83036 KB Output is correct
6 Correct 95 ms 83136 KB Output is correct
7 Correct 317 ms 83536 KB Output is correct
8 Correct 581 ms 84412 KB Output is correct
9 Correct 148 ms 141648 KB Output is correct
10 Correct 260 ms 140908 KB Output is correct
11 Correct 615 ms 141176 KB Output is correct
12 Correct 1142 ms 141436 KB Output is correct
13 Correct 289 ms 213532 KB Output is correct
14 Correct 368 ms 213592 KB Output is correct
15 Correct 973 ms 213836 KB Output is correct
16 Correct 1666 ms 214344 KB Output is correct
17 Correct 3471 ms 214172 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 202612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 68180 KB Output is correct
2 Correct 32 ms 68152 KB Output is correct
3 Correct 32 ms 68232 KB Output is correct
4 Correct 32 ms 68184 KB Output is correct
5 Correct 31 ms 68052 KB Output is correct
6 Correct 32 ms 68188 KB Output is correct
7 Correct 36 ms 68184 KB Output is correct
8 Correct 36 ms 68188 KB Output is correct
9 Correct 31 ms 68180 KB Output is correct
10 Correct 40 ms 68072 KB Output is correct
11 Correct 34 ms 68176 KB Output is correct
12 Correct 31 ms 68180 KB Output is correct
13 Correct 39 ms 68180 KB Output is correct
14 Correct 32 ms 68272 KB Output is correct
15 Correct 32 ms 68176 KB Output is correct
16 Correct 32 ms 68188 KB Output is correct
17 Correct 41 ms 68180 KB Output is correct
18 Correct 33 ms 68192 KB Output is correct
19 Correct 51 ms 69764 KB Output is correct
20 Correct 49 ms 69696 KB Output is correct
21 Correct 48 ms 69716 KB Output is correct
22 Correct 59 ms 69736 KB Output is correct
23 Correct 78 ms 75604 KB Output is correct
24 Correct 76 ms 75600 KB Output is correct
25 Correct 108 ms 75652 KB Output is correct
26 Correct 109 ms 76036 KB Output is correct
27 Correct 25 ms 68180 KB Output is correct
28 Correct 26 ms 68184 KB Output is correct
29 Correct 29 ms 68304 KB Output is correct
30 Correct 40 ms 68432 KB Output is correct
31 Correct 80 ms 69204 KB Output is correct
32 Correct 29 ms 68200 KB Output is correct
33 Correct 25 ms 68944 KB Output is correct
34 Correct 25 ms 68944 KB Output is correct
35 Correct 32 ms 68956 KB Output is correct
36 Correct 41 ms 69152 KB Output is correct
37 Correct 106 ms 69984 KB Output is correct
38 Correct 37 ms 75600 KB Output is correct
39 Correct 37 ms 75416 KB Output is correct
40 Correct 34 ms 75668 KB Output is correct
41 Correct 54 ms 75860 KB Output is correct
42 Correct 145 ms 76624 KB Output is correct
43 Correct 224 ms 213720 KB Output is correct
44 Correct 204 ms 213568 KB Output is correct
45 Correct 204 ms 213572 KB Output is correct
46 Correct 229 ms 213808 KB Output is correct
47 Correct 478 ms 214848 KB Output is correct
48 Correct 30 ms 69712 KB Output is correct
49 Correct 56 ms 69716 KB Output is correct
50 Correct 167 ms 70228 KB Output is correct
51 Correct 317 ms 70868 KB Output is correct
52 Correct 51 ms 83036 KB Output is correct
53 Correct 95 ms 83136 KB Output is correct
54 Correct 317 ms 83536 KB Output is correct
55 Correct 581 ms 84412 KB Output is correct
56 Correct 148 ms 141648 KB Output is correct
57 Correct 260 ms 140908 KB Output is correct
58 Correct 615 ms 141176 KB Output is correct
59 Correct 1142 ms 141436 KB Output is correct
60 Correct 289 ms 213532 KB Output is correct
61 Correct 368 ms 213592 KB Output is correct
62 Correct 973 ms 213836 KB Output is correct
63 Correct 1666 ms 214344 KB Output is correct
64 Correct 3471 ms 214172 KB Output is correct
65 Incorrect 115 ms 202612 KB Output isn't correct
66 Halted 0 ms 0 KB -