oj.uz

Submission #532685

# Submission time Handle Problem Language Result Execution time Memory
532685 2022-03-03T15:56:41 Z mat50013 Dynamic Diameter (CEOI19_diameter) C++11
100 / 100
 4157 ms 220228 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int NMAX(100005);
vector<pair<int, ll> > G[NMAX];
vector<pair<int, int> > frati[NMAX];
multiset<ll> vec[NMAX];
map<int, ll> cum[NMAX];
map<pair<int, int>, vector<pair<int, int> > > mp;
bool dead[NMAX], mark[NMAX], viz[NMAX];
int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
ll dist[NMAX], maxx[NMAX];

struct SEGTREE
{
    vector<ll> Arb, lazy;
    vector<int> in, out;
    int cati;
    inline void init(int n)
    {
        cati = n;
        int put = 1;
        while(put <= n)
            put <<= 1;
        put <<= 1;
        Arb.resize(put), in.resize(put), out.resize(put), lazy.resize(put << 1);
    }
    inline void build(int nod, int st, int dr)
    {
        if(st == dr)
        {
            Arb[nod] = dist[st];
            return;
        }
        int mij = (st + dr) / 2;
        build(2 * nod, st, mij);
        build(2 * nod + 1, mij + 1, dr);
        Arb[nod] = max(Arb[2 * nod], Arb[2 * nod + 1]);
    }
    inline void push(int nod)
    {
        if(lazy[nod])
        {
            Arb[nod] += lazy[nod];
            lazy[2 * nod] += lazy[nod];
            lazy[2 * nod + 1] += lazy[nod];
            lazy[nod] = 0;
        }
    }
    inline void update(int nod, int st, int dr, int a, int b, ll val)
    {
        if(a <= st && dr <= b)
        {
            lazy[nod] += val;
            push(nod);
            return;
        }
        push(nod);
        int mij = (st + dr) / 2;
        if(a <= mij)
            update(2 * nod, st, mij, a, b, val);
        if(b > mij)
            update(2 * nod + 1, mij + 1, dr, a, b, val);
        push(2 * nod), push(2 * nod + 1);
        Arb[nod] = max(Arb[2 * nod], Arb[2 * nod + 1]);
    }
    inline ll query(int nod, int st, int dr, int a, int b)
    {
        push(nod);
        if(a <= st && dr <= b)
            return Arb[nod];
        int mij = (st + dr) / 2;
        ll rez1 = 0, rez2 = 0;
        if(a <= mij)
            rez1 = query(2 * nod, st, mij, a, b);
        if(b > mij)
            rez2 = query(2 * nod + 1, mij + 1, dr, a, b);
        return max(rez1, rez2);
    }
} interv[NMAX];

inline int getC(int nod)
{
    viz[nod] = 1;
    sz[nod] = 1;
    int maxx = 0;
    for(auto it: G[nod])
        if(!viz[it.first] && mark[it.first])
        {
            int c = getC(it.first);
            if(c != -1)
                return c;
            sz[nod] += sz[it.first];
            maxx = max(maxx, sz[it.first]);
        }
    maxx = max(maxx, dim - sz[nod]);
    if(maxx <= dim / 2)
        return nod;
    return -1;
}

inline void DFS(int nod)
{
    viz[nod] = 1;
    tip[nod] = cnt;
    for(auto it: G[nod])
        if(!viz[it.first] && mark[it.first])
            DFS(it.first);
}

inline void buildTree(int nod, int tata = -1)
{
    interv[baza].in[id[nod]] = ++mov;
    for(auto it: G[nod])
        if(tata != it.first && mark[it.first])
        {
            mp[ {min(it.first, nod), max(it.first, nod)}].push_back({id[it.first], baza});
            dist[mov + 1] = dist[interv[baza].in[id[nod]]] + it.second;
            buildTree(it.first, nod);
        }
    interv[baza].out[id[nod]] = mov;
}

inline void centroidDecomp(vector<int> nodes)
{
    if(nodes.size() == 1)
        return;
    int mr = 0;
    for(auto it: nodes)
        mark[it] = 1, sz[it] = tip[it] = 0, viz[it] = 0, id[it] = ++mr;

    dim = nodes.size();
    int cen = getC(nodes[0]);
    baza = cen;
    mov = dist[1] = 0;
    interv[baza].init(nodes.size());
    buildTree(cen);
    interv[baza].build(1, 1, nodes.size());

    for(auto it: nodes)
        viz[it] = 0;
    viz[cen] = 1;
    cnt = 0;
    for(auto it: G[cen])
        if(!viz[it.first] && mark[it.first])
        {
            frati[cen].push_back({interv[baza].in[id[it.first]], id[it.first]});
            ++cnt;
            DFS(it.first);
        }
    vector<vector<int> > nex(cnt + 1);
    for(auto it: nodes)
        nex[tip[it]].push_back(it);

    for(auto it: nodes)
        mark[it] = 0, sz[it] = tip[it] = 0, viz[it] = 0;
    int nn = cnt;
    for(int i = 1; i <= nn; ++i)
        centroidDecomp(nex[i]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, q;
    ll w;
    cin >> n >> q >> w;

    vector<tuple<int, int, ll> > Muchie;
    for(int i = 1; i < n; ++i)
    {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        Muchie.push_back(make_tuple(min(a, b), max(a, b), c));
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }

    vector<int> noduri;
    for(int i = 1; i <= n; ++i)
        noduri.push_back(i);
    centroidDecomp(noduri);

    auto calc = [](int i, bool da)
    {
        if(da)
        {
            for(auto it: frati[i])
            {
                ll val = interv[i].query(1, 1, interv[i].cati, interv[i].in[it.second], interv[i].out[it.second]);
                vec[i].insert(val);
                cum[i][it.second] = val;
            }
        }
        auto it = vec[i].end();
        --it;
        ll rz = *it;
        if(vec[i].size() >= 2)
        {
            --it;
            rz += *it;
        }
        return rz;
    };

    multiset<ll> s;
    for(int i = 1; i <= n; ++i)
        if(frati[i].size())
            maxx[i] = calc(i, 1), s.insert(-maxx[i]);
    ll last = 0;
    for(int i = 1; i <= q; ++i)
    {
        int d;
        ll e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;

        int x, y;
        ll c;
        tie(x, y, c) = Muchie[d];
        for(auto it: mp[ {x, y}])
        {
            interv[it.second].update(1, 1, interv[it.second].cati, interv[it.second].in[it.first], interv[it.second].out[it.first], e - c);
            auto ind = upper_bound(frati[it.second].begin(), frati[it.second].end(), make_pair(interv[it.second].in[it.first], 2 * NMAX));
            --ind;
            int careF = ind->second;
            ll newV = interv[it.second].query(1, 1, interv[it.second].cati, interv[it.second].in[careF], interv[it.second].out[careF]);
            vec[it.second].erase(vec[it.second].find(cum[it.second][careF]));
            vec[it.second].insert(newV);
            cum[it.second][careF] = newV;
            s.erase(s.find(-maxx[it.second]));
            maxx[it.second] = calc(it.second, 0);
            s.insert(-maxx[it.second]);
        }
        Muchie[d] = make_tuple(x, y, e);
        cout << -*s.begin() << '\n';
        last = -*s.begin();
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24524 KB Output is correct
2 Correct 12 ms 24564 KB Output is correct
3 Correct 12 ms 24524 KB Output is correct
4 Correct 13 ms 24524 KB Output is correct
5 Correct 13 ms 24524 KB Output is correct
6 Correct 14 ms 24524 KB Output is correct
7 Correct 15 ms 24524 KB Output is correct
8 Correct 16 ms 24640 KB Output is correct
9 Correct 14 ms 24584 KB Output is correct
10 Correct 13 ms 24604 KB Output is correct
11 Correct 13 ms 24588 KB Output is correct
12 Correct 12 ms 24540 KB Output is correct
13 Correct 13 ms 24608 KB Output is correct
14 Correct 15 ms 24652 KB Output is correct
15 Correct 13 ms 24652 KB Output is correct
16 Correct 17 ms 24616 KB Output is correct
17 Correct 12 ms 24652 KB Output is correct
18 Correct 13 ms 24712 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24524 KB Output is correct
2 Correct 12 ms 24564 KB Output is correct
3 Correct 12 ms 24524 KB Output is correct
4 Correct 13 ms 24524 KB Output is correct
5 Correct 13 ms 24524 KB Output is correct
6 Correct 14 ms 24524 KB Output is correct
7 Correct 15 ms 24524 KB Output is correct
8 Correct 16 ms 24640 KB Output is correct
9 Correct 14 ms 24584 KB Output is correct
10 Correct 13 ms 24604 KB Output is correct
11 Correct 13 ms 24588 KB Output is correct
12 Correct 12 ms 24540 KB Output is correct
13 Correct 13 ms 24608 KB Output is correct
14 Correct 15 ms 24652 KB Output is correct
15 Correct 13 ms 24652 KB Output is correct
16 Correct 17 ms 24616 KB Output is correct
17 Correct 12 ms 24652 KB Output is correct
18 Correct 13 ms 24712 KB Output is correct
19 Correct 35 ms 25540 KB Output is correct
20 Correct 32 ms 25664 KB Output is correct
21 Correct 38 ms 25628 KB Output is correct
22 Correct 39 ms 25816 KB Output is correct
23 Correct 70 ms 29972 KB Output is correct
24 Correct 71 ms 31192 KB Output is correct
25 Correct 68 ms 32056 KB Output is correct
26 Correct 78 ms 33424 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24536 KB Output is correct
2 Correct 12 ms 24516 KB Output is correct
3 Correct 18 ms 24588 KB Output is correct
4 Correct 26 ms 24780 KB Output is correct
5 Correct 76 ms 25732 KB Output is correct
6 Correct 16 ms 24512 KB Output is correct
7 Correct 14 ms 24780 KB Output is correct
8 Correct 14 ms 24748 KB Output is correct
9 Correct 16 ms 24780 KB Output is correct
10 Correct 33 ms 25028 KB Output is correct
11 Correct 107 ms 26052 KB Output is correct
12 Correct 19 ms 26696 KB Output is correct
13 Correct 20 ms 26772 KB Output is correct
14 Correct 21 ms 26828 KB Output is correct
15 Correct 57 ms 27012 KB Output is correct
16 Correct 157 ms 28228 KB Output is correct
17 Correct 177 ms 65536 KB Output is correct
18 Correct 182 ms 65528 KB Output is correct
19 Correct 183 ms 65472 KB Output is correct
20 Correct 249 ms 65768 KB Output is correct
21 Correct 655 ms 66248 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 25616 KB Output is correct
2 Correct 45 ms 25676 KB Output is correct
3 Correct 164 ms 26256 KB Output is correct
4 Correct 268 ms 26940 KB Output is correct
5 Correct 52 ms 37696 KB Output is correct
6 Correct 92 ms 37852 KB Output is correct
7 Correct 303 ms 38520 KB Output is correct
8 Correct 569 ms 39304 KB Output is correct
9 Correct 268 ms 96940 KB Output is correct
10 Correct 300 ms 97148 KB Output is correct
11 Correct 686 ms 97644 KB Output is correct
12 Correct 1134 ms 97924 KB Output is correct
13 Correct 446 ms 175264 KB Output is correct
14 Correct 590 ms 175228 KB Output is correct
15 Correct 1006 ms 175652 KB Output is correct
16 Correct 1608 ms 175920 KB Output is correct
17 Correct 3103 ms 175892 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3041 ms 172252 KB Output is correct
2 Correct 3126 ms 176048 KB Output is correct
3 Correct 3042 ms 174648 KB Output is correct
4 Correct 3011 ms 176988 KB Output is correct
5 Correct 2843 ms 169448 KB Output is correct
6 Correct 2477 ms 127020 KB Output is correct
7 Correct 3961 ms 204188 KB Output is correct
8 Correct 3952 ms 204332 KB Output is correct
9 Correct 4157 ms 204140 KB Output is correct
10 Correct 3982 ms 203560 KB Output is correct
11 Correct 3762 ms 193808 KB Output is correct
12 Correct 3027 ms 143648 KB Output is correct
13 Correct 3813 ms 217656 KB Output is correct
14 Correct 3852 ms 217472 KB Output is correct
15 Correct 3793 ms 217628 KB Output is correct
16 Correct 3844 ms 216676 KB Output is correct
17 Correct 3657 ms 206204 KB Output is correct
18 Correct 2854 ms 149576 KB Output is correct
19 Correct 4115 ms 216964 KB Output is correct
20 Correct 3869 ms 216656 KB Output is correct
21 Correct 3891 ms 216584 KB Output is correct
22 Correct 3846 ms 215800 KB Output is correct
23 Correct 3529 ms 205484 KB Output is correct
24 Correct 2804 ms 148716 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24524 KB Output is correct
2 Correct 12 ms 24564 KB Output is correct
3 Correct 12 ms 24524 KB Output is correct
4 Correct 13 ms 24524 KB Output is correct
5 Correct 13 ms 24524 KB Output is correct
6 Correct 14 ms 24524 KB Output is correct
7 Correct 15 ms 24524 KB Output is correct
8 Correct 16 ms 24640 KB Output is correct
9 Correct 14 ms 24584 KB Output is correct
10 Correct 13 ms 24604 KB Output is correct
11 Correct 13 ms 24588 KB Output is correct
12 Correct 12 ms 24540 KB Output is correct
13 Correct 13 ms 24608 KB Output is correct
14 Correct 15 ms 24652 KB Output is correct
15 Correct 13 ms 24652 KB Output is correct
16 Correct 17 ms 24616 KB Output is correct
17 Correct 12 ms 24652 KB Output is correct
18 Correct 13 ms 24712 KB Output is correct
19 Correct 35 ms 25540 KB Output is correct
20 Correct 32 ms 25664 KB Output is correct
21 Correct 38 ms 25628 KB Output is correct
22 Correct 39 ms 25816 KB Output is correct
23 Correct 70 ms 29972 KB Output is correct
24 Correct 71 ms 31192 KB Output is correct
25 Correct 68 ms 32056 KB Output is correct
26 Correct 78 ms 33424 KB Output is correct
27 Correct 12 ms 24536 KB Output is correct
28 Correct 12 ms 24516 KB Output is correct
29 Correct 18 ms 24588 KB Output is correct
30 Correct 26 ms 24780 KB Output is correct
31 Correct 76 ms 25732 KB Output is correct
32 Correct 16 ms 24512 KB Output is correct
33 Correct 14 ms 24780 KB Output is correct
34 Correct 14 ms 24748 KB Output is correct
35 Correct 16 ms 24780 KB Output is correct
36 Correct 33 ms 25028 KB Output is correct
37 Correct 107 ms 26052 KB Output is correct
38 Correct 19 ms 26696 KB Output is correct
39 Correct 20 ms 26772 KB Output is correct
40 Correct 21 ms 26828 KB Output is correct
41 Correct 57 ms 27012 KB Output is correct
42 Correct 157 ms 28228 KB Output is correct
43 Correct 177 ms 65536 KB Output is correct
44 Correct 182 ms 65528 KB Output is correct
45 Correct 183 ms 65472 KB Output is correct
46 Correct 249 ms 65768 KB Output is correct
47 Correct 655 ms 66248 KB Output is correct
48 Correct 18 ms 25616 KB Output is correct
49 Correct 45 ms 25676 KB Output is correct
50 Correct 164 ms 26256 KB Output is correct
51 Correct 268 ms 26940 KB Output is correct
52 Correct 52 ms 37696 KB Output is correct
53 Correct 92 ms 37852 KB Output is correct
54 Correct 303 ms 38520 KB Output is correct
55 Correct 569 ms 39304 KB Output is correct
56 Correct 268 ms 96940 KB Output is correct
57 Correct 300 ms 97148 KB Output is correct
58 Correct 686 ms 97644 KB Output is correct
59 Correct 1134 ms 97924 KB Output is correct
60 Correct 446 ms 175264 KB Output is correct
61 Correct 590 ms 175228 KB Output is correct
62 Correct 1006 ms 175652 KB Output is correct
63 Correct 1608 ms 175920 KB Output is correct
64 Correct 3103 ms 175892 KB Output is correct
65 Correct 3041 ms 172252 KB Output is correct
66 Correct 3126 ms 176048 KB Output is correct
67 Correct 3042 ms 174648 KB Output is correct
68 Correct 3011 ms 176988 KB Output is correct
69 Correct 2843 ms 169448 KB Output is correct
70 Correct 2477 ms 127020 KB Output is correct
71 Correct 3961 ms 204188 KB Output is correct
72 Correct 3952 ms 204332 KB Output is correct
73 Correct 4157 ms 204140 KB Output is correct
74 Correct 3982 ms 203560 KB Output is correct
75 Correct 3762 ms 193808 KB Output is correct
76 Correct 3027 ms 143648 KB Output is correct
77 Correct 3813 ms 217656 KB Output is correct
78 Correct 3852 ms 217472 KB Output is correct
79 Correct 3793 ms 217628 KB Output is correct
80 Correct 3844 ms 216676 KB Output is correct
81 Correct 3657 ms 206204 KB Output is correct
82 Correct 2854 ms 149576 KB Output is correct
83 Correct 4115 ms 216964 KB Output is correct
84 Correct 3869 ms 216656 KB Output is correct
85 Correct 3891 ms 216584 KB Output is correct
86 Correct 3846 ms 215800 KB Output is correct
87 Correct 3529 ms 205484 KB Output is correct
88 Correct 2804 ms 148716 KB Output is correct
89 Correct 2805 ms 176168 KB Output is correct
90 Correct 3134 ms 187840 KB Output is correct
91 Correct 3515 ms 202288 KB Output is correct
92 Correct 3647 ms 206512 KB Output is correct
93 Correct 3818 ms 211292 KB Output is correct
94 Correct 3793 ms 215488 KB Output is correct
95 Correct 3788 ms 220004 KB Output is correct
96 Correct 3851 ms 220000 KB Output is correct
97 Correct 3812 ms 220044 KB Output is correct
98 Correct 3662 ms 219944 KB Output is correct
99 Correct 3688 ms 220056 KB Output is correct
100 Correct 3631 ms 220228 KB Output is correct