oj.uz

Submission #971953

# Submission time Handle Problem Language Result Execution time Memory
971953 2024-04-29T14:59:11 Z efedmrlr Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 4123 ms 271624 KB 
#include <bits/stdc++.h>
#define int long long int
#define lli 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][centro] = 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});
    }

    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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 111708 KB Output is correct
2 Correct 30 ms 111708 KB Output is correct
3 Incorrect 32 ms 111708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 111708 KB Output is correct
2 Correct 30 ms 111708 KB Output is correct
3 Incorrect 32 ms 111708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 111696 KB Output is correct
2 Correct 32 ms 111700 KB Output is correct
3 Correct 32 ms 111700 KB Output is correct
4 Correct 44 ms 111708 KB Output is correct
5 Correct 85 ms 111924 KB Output is correct
6 Correct 35 ms 111704 KB Output is correct
7 Correct 31 ms 112372 KB Output is correct
8 Correct 31 ms 112208 KB Output is correct
9 Correct 34 ms 112196 KB Output is correct
10 Correct 48 ms 112468 KB Output is correct
11 Correct 111 ms 112712 KB Output is correct
12 Correct 36 ms 119132 KB Output is correct
13 Correct 41 ms 119104 KB Output is correct
14 Correct 44 ms 118936 KB Output is correct
15 Correct 60 ms 119116 KB Output is correct
16 Correct 146 ms 119524 KB Output is correct
17 Correct 204 ms 258116 KB Output is correct
18 Correct 190 ms 257984 KB Output is correct
19 Correct 194 ms 258116 KB Output is correct
20 Correct 231 ms 258448 KB Output is correct
21 Correct 441 ms 258624 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 112980 KB Output is correct
2 Correct 59 ms 113008 KB Output is correct
3 Incorrect 204 ms 113460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2414 ms 261288 KB Output is correct
2 Correct 2462 ms 261180 KB Output is correct
3 Correct 2485 ms 261296 KB Output is correct
4 Correct 2424 ms 260852 KB Output is correct
5 Correct 2374 ms 261096 KB Output is correct
6 Correct 2086 ms 260172 KB Output is correct
7 Correct 3373 ms 263296 KB Output is correct
8 Correct 3325 ms 263576 KB Output is correct
9 Correct 3389 ms 263428 KB Output is correct
10 Correct 3296 ms 265064 KB Output is correct
11 Correct 3330 ms 267200 KB Output is correct
12 Correct 2962 ms 266656 KB Output is correct
13 Correct 3782 ms 271192 KB Output is correct
14 Correct 3818 ms 271624 KB Output is correct
15 Correct 3821 ms 271040 KB Output is correct
16 Correct 4002 ms 270996 KB Output is correct
17 Correct 4022 ms 270612 KB Output is correct
18 Correct 3440 ms 268268 KB Output is correct
19 Correct 4123 ms 271204 KB Output is correct
20 Correct 3792 ms 271340 KB Output is correct
21 Correct 3840 ms 271304 KB Output is correct
22 Correct 3867 ms 271060 KB Output is correct
23 Correct 3768 ms 270808 KB Output is correct
24 Correct 3226 ms 268404 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 111708 KB Output is correct
2 Correct 30 ms 111708 KB Output is correct
3 Incorrect 32 ms 111708 KB Output isn't correct
4 Halted 0 ms 0 KB -