Submission #557586

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
557586	2022-05-05T14:13:40 Z	RaresFelix	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	1649 ms	159984 KB

diameter

#include <bits/stdc++.h>
#define MN 100071

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
ll n, q, max_weight;
vector<ii> L[MN];
namespace AINT {
    /// A shared data structure between centroids for best 2 numbers in interval
    ll V[2][4 * MN], Lazy[4 * MN], len;

    void init(int l0) {
        len = l0;
        for(int i = 1; i <= 4 * len; ++i)
            V[1][i] = -(1ll << 60);
    }

    inline void prop(ll u, ll s, ll d) {
        if(!Lazy[u]) return;
        V[0][u] += Lazy[u], V[1][u] += Lazy[u];
        if(s != d) {
            Lazy[u << 1] += Lazy[u];
            Lazy[u << 1 | 1] += Lazy[u];
        }
        Lazy[u] = 0;
    }

    void add(ll l, ll r, ll v, ll u = 1, ll s = 1, ll d = len) {
        if(d < l || r < s) return;
        prop(u, s, d);
        if(l <= s && d <= r) {
            Lazy[u] += v;
            prop(u, s, d);
            //printf("    Dupa un add la %d(%d, %d) am modificat maximele la %d si %d\n", u, s, d, V[0][u], V[1][u]);
            return;
        }
        add(l, r, v, u << 1, s, (s + d) >> 1);
        add(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        ll p1 = 0, p2 = 0;
        for(ll p = 0; p < 2; ++p) {
            if(V[p1][u << 1] > V[p2][u << 1 | 1]) V[p][u] = V[p1++][u << 1];
            else V[p][u] = V[p2++][u << 1 | 1];
        }
        //printf("    Dupa un add la %d(%d, %d) am modificat maximele la %d si %d\n", u, s, d, V[0][u], V[1][u]);
    }
    
    pair<ll, ll> query(ll l, ll r, ll u = 1, ll s = 1, ll d = len) {
        prop(u, s, d);
        if(r < s || d < l) return {0, 0};
        if(l <= s && d <= r) 
            return {V[0][u], V[1][u]};
        auto [a, b] = query(l, r, u << 1, s, (s + d) >> 1);
        auto [x, y] = query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d);
        vector<ll> A = {a, b, x, y};
        sort(A.begin(), A.end());
        return {A[3], A[2]};
    }
};
map<ii, ll> Eid;
ii E[MN];
vector<ii> PozAfectate[MN]; // pt fiecare muchie, seg afectate in aint
vector<ii> trees; // seg pe aint ce reprezinta un centroid
vector<ll> ArbAfectati[MN]; // pt fiecare muchie, in ce seg de centr se afla

multiset<ii> bestByTree; // {sum, tree_id}
map<int, ll> ValoareArb;

void add_tree(ll u) {
    auto [st, dr] = trees[u];
    auto [a, b] = AINT::query(st, dr);
    //printf("La o modificare a arborelui %d(cu lim %d si %d) am gasit 2 maxime: %d si %d\n", u, st, dr, a, b);
    ValoareArb[u] = a + b;
    bestByTree.insert({a + b, u});
}

int W[MN];

void init() {
    cin >> n >> q >> max_weight;
    for(int i = 1; i < n; ++i) {
        ll u, v, w;
        cin >> u >> v >> w;
        E[i] = {u, v};
        W[i] = w;
        Eid[E[i]] = i; Eid[{v, u}] = i;
        L[u].push_back({v, w});
        L[v].push_back({u, w});
    }
    vector<int> Cpar(n + 1, 0), Sz(n + 1, 0);
    vector<bool> Used(n + 1, false);
    function<void(int, int)> dfi = [&] (int u, int p) {
        Sz[u] = 1;
        for(auto [it, w] : L[u])
            if(!Used[it] && it != p) dfi(it, u), Sz[u] += Sz[it];
    };
    function<int(int, int, int)> find_centroid = [&] (int u, int p, int bsz) {
        for(auto [it, w] : L[u])
            if(it != p && !Used[it] && Sz[it] * 2 > bsz) return find_centroid(it, u, bsz);
        return u;
    };
    int global_tmr = 0;
    function<void(int, int)> init_aint = [&] (int u, int p) {
        int st = global_tmr + 1;
        if(int(L[u].size()) == 1) { /// a leaf
            ++global_tmr;
        }   
        for(auto [it, w] : L[u])
            if(!Used[it] && it != p) init_aint(it, u);
        int dr = global_tmr;
        PozAfectate[Eid[{u, p}]].push_back({st, dr});
    };
    function<void(int, int, int)> dfs_afect = [&](int u, int p, int dest) {
        if(p) ArbAfectati[Eid[{u, p}]].push_back(dest);
        for(auto [it, w] : L[u])
            if(!Used[it] && it != p)
                dfs_afect(it, u, dest);
    };
    function<void(int, int)> desc = [&] (int u, int cpar) {
        int st = global_tmr + 1;
        dfi(u, 0);
        int c = find_centroid(u, 0, Sz[u]);
        Used[c] = 1;
        Cpar[c] = cpar;
        init_aint(c, 0);
        int dr = global_tmr;

        trees.push_back({st, 0});
        trees[int(trees.size()) - 1].second = dr;
        //printf("L-am scos pe %d ca centroid de la %d la %d\n", c, st, dr);
        dfs_afect(c, 0, int(trees.size()) - 1);
        for(auto [it, w] : L[c])
            if(!Used[it]) desc(it, c);
    };
    //printf("--------------------------\n");
    desc(1, 0);
    //printf("--------------------------\n");
    AINT::init(global_tmr + 1);
    for(int i = 1; i < n; ++i) {
        auto [u, v] = E[i];
        int w = W[i];
        //printf("Muchia %d afecteaza segmentele: ", i);
        for(auto [st, dr] : PozAfectate[i]) {
            AINT::add(st, dr, w);
            //printf(" & (%d, %d)", st, dr);
        } 
        //printf("\n");
    }
    //printf("--------------------------\n");
    for(int i = 0; i < trees.size(); ++i) add_tree(i);
}
void update(int muchie, ll w) {
    ll lw = W[muchie], delta = w - lw;
    //printf("Muchia %d %d isi schimba valoarea %d -> %d\n", E[muchie].first, E[muchie].second, lw, w);
    for(auto [st, dr] : PozAfectate[muchie]) {
        AINT::add(st, dr, delta);
    }
    W[muchie] = w;
    for(auto it : ArbAfectati[muchie])
        bestByTree.erase({ValoareArb[it], it});
    for(auto it : ArbAfectati[muchie])
        add_tree(it);
}
int main() {
    init();
    ll last = 0;
    for(int i = 1; i <= q; ++i) {
        int d; ll e;
        cin >> d >> e;
        d = (d + last) % (n - 1) + 1;
        e = (e + last) % max_weight;
        update(d, e);
        auto [v, id] = *bestByTree.rbegin();
        cout << v << "\n";
        last = v;
    }
    return 0;
}

Compilation message

diameter.cpp: In function 'void init()':
diameter.cpp:140:14: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  140 |         auto [u, v] = E[i];
      |              ^~~~~~
diameter.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for(int i = 0; i < trees.size(); ++i) add_tree(i);
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Correct	4 ms	7380 KB	Output is correct
3	Correct	9 ms	7420 KB	Output is correct
4	Correct	49 ms	7580 KB	Output is correct
5	Correct	270 ms	8408 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	6 ms	7636 KB	Output is correct
8	Correct	6 ms	7636 KB	Output is correct
9	Correct	10 ms	7632 KB	Output is correct
10	Correct	60 ms	7884 KB	Output is correct
11	Correct	267 ms	8904 KB	Output is correct
12	Correct	17 ms	10324 KB	Output is correct
13	Correct	17 ms	10420 KB	Output is correct
14	Correct	24 ms	10384 KB	Output is correct
15	Correct	84 ms	10720 KB	Output is correct
16	Correct	341 ms	11860 KB	Output is correct
17	Runtime error	248 ms	94428 KB	Execution killed with signal 11
18	Halted	0 ms	0 KB	-