Submission #971948

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
971948	2024-04-29T14:49:03 Z	efedmrlr	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	445 ms	213316 KB

diameter

#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][centro] = 0;
    prec3(centro, 0, lvl);
    
    vis[centro] = 1;
    for(auto c : adj[node]) {
        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}));
            assert(rep == (*itr)[0]);
            // 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	Incorrect	27 ms	68188 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

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

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	68176 KB	Output is correct
2	Correct	26 ms	68012 KB	Output is correct
3	Correct	26 ms	68188 KB	Output is correct
4	Correct	36 ms	68188 KB	Output is correct
5	Correct	77 ms	68652 KB	Output is correct
6	Correct	25 ms	68188 KB	Output is correct
7	Correct	29 ms	68944 KB	Output is correct
8	Correct	27 ms	68956 KB	Output is correct
9	Correct	27 ms	68944 KB	Output is correct
10	Correct	52 ms	69028 KB	Output is correct
11	Correct	108 ms	69200 KB	Output is correct
12	Correct	33 ms	75548 KB	Output is correct
13	Correct	34 ms	75356 KB	Output is correct
14	Correct	35 ms	75612 KB	Output is correct
15	Correct	54 ms	75596 KB	Output is correct
16	Correct	144 ms	75904 KB	Output is correct
17	Correct	183 ms	212544 KB	Output is correct
18	Correct	197 ms	212576 KB	Output is correct
19	Correct	189 ms	212544 KB	Output is correct
20	Correct	236 ms	212672 KB	Output is correct
21	Correct	445 ms	213316 KB	Output is correct