oj.uz

Submission #532681

# Submission time Handle Problem Language Result Execution time Memory
532681 2022-03-03T15:39:02 Z mat50013 Dynamic Diameter (CEOI19_diameter) C++11
66 / 100
 5000 ms 220872 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int NMAX(100005);
vector<pair<int, ll> > G[NMAX];
vector<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(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]);
}
//ifstream fin("date.in");
//ofstream fout("date.out");
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], interv[i].out[it]);
                vec[i].insert(val);
                cum[i][it] = 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);
            for(auto careF: frati[it.second])
                if(interv[it.second].in[careF] <= interv[it.second].in[it.first] && interv[it.second].in[it.first] <= interv[it.second].out[careF])
                {
                    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;
                    break;
                }
            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 14 ms 24604 KB Output is correct
3 Correct 14 ms 24584 KB Output is correct
4 Correct 14 ms 24524 KB Output is correct
5 Correct 13 ms 24604 KB Output is correct
6 Correct 13 ms 24596 KB Output is correct
7 Correct 13 ms 24524 KB Output is correct
8 Correct 13 ms 24652 KB Output is correct
9 Correct 13 ms 24620 KB Output is correct
10 Correct 15 ms 24524 KB Output is correct
11 Correct 14 ms 24648 KB Output is correct
12 Correct 13 ms 24592 KB Output is correct
13 Correct 13 ms 24576 KB Output is correct
14 Correct 15 ms 24628 KB Output is correct
15 Correct 15 ms 24668 KB Output is correct
16 Correct 15 ms 24668 KB Output is correct
17 Correct 14 ms 24652 KB Output is correct
18 Correct 14 ms 24592 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 14 ms 24604 KB Output is correct
3 Correct 14 ms 24584 KB Output is correct
4 Correct 14 ms 24524 KB Output is correct
5 Correct 13 ms 24604 KB Output is correct
6 Correct 13 ms 24596 KB Output is correct
7 Correct 13 ms 24524 KB Output is correct
8 Correct 13 ms 24652 KB Output is correct
9 Correct 13 ms 24620 KB Output is correct
10 Correct 15 ms 24524 KB Output is correct
11 Correct 14 ms 24648 KB Output is correct
12 Correct 13 ms 24592 KB Output is correct
13 Correct 13 ms 24576 KB Output is correct
14 Correct 15 ms 24628 KB Output is correct
15 Correct 15 ms 24668 KB Output is correct
16 Correct 15 ms 24668 KB Output is correct
17 Correct 14 ms 24652 KB Output is correct
18 Correct 14 ms 24592 KB Output is correct
19 Correct 31 ms 25488 KB Output is correct
20 Correct 35 ms 25668 KB Output is correct
21 Correct 37 ms 25736 KB Output is correct
22 Correct 38 ms 25860 KB Output is correct
23 Correct 56 ms 29840 KB Output is correct
24 Correct 66 ms 31208 KB Output is correct
25 Correct 72 ms 32068 KB Output is correct
26 Correct 76 ms 33520 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24524 KB Output is correct
2 Correct 13 ms 24576 KB Output is correct
3 Correct 15 ms 24540 KB Output is correct
4 Correct 26 ms 24780 KB Output is correct
5 Correct 73 ms 25716 KB Output is correct
6 Correct 13 ms 24572 KB Output is correct
7 Correct 16 ms 24720 KB Output is correct
8 Correct 14 ms 24820 KB Output is correct
9 Correct 17 ms 24848 KB Output is correct
10 Correct 42 ms 25024 KB Output is correct
11 Correct 129 ms 26020 KB Output is correct
12 Correct 21 ms 26692 KB Output is correct
13 Correct 21 ms 26772 KB Output is correct
14 Correct 26 ms 26816 KB Output is correct
15 Correct 100 ms 27028 KB Output is correct
16 Correct 418 ms 28124 KB Output is correct
17 Correct 185 ms 65072 KB Output is correct
18 Correct 199 ms 65100 KB Output is correct
19 Correct 286 ms 65264 KB Output is correct
20 Correct 1329 ms 65720 KB Output is correct
21 Execution timed out 5032 ms 66568 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 25548 KB Output is correct
2 Correct 44 ms 25716 KB Output is correct
3 Correct 144 ms 26192 KB Output is correct
4 Correct 280 ms 26864 KB Output is correct
5 Correct 52 ms 37772 KB Output is correct
6 Correct 99 ms 37844 KB Output is correct
7 Correct 300 ms 38520 KB Output is correct
8 Correct 550 ms 39368 KB Output is correct
9 Correct 224 ms 97000 KB Output is correct
10 Correct 304 ms 97172 KB Output is correct
11 Correct 661 ms 97716 KB Output is correct
12 Correct 1059 ms 98708 KB Output is correct
13 Correct 456 ms 175820 KB Output is correct
14 Correct 545 ms 175796 KB Output is correct
15 Correct 1004 ms 176520 KB Output is correct
16 Correct 1495 ms 177456 KB Output is correct
17 Correct 2717 ms 177248 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2739 ms 174424 KB Output is correct
2 Correct 2876 ms 178520 KB Output is correct
3 Correct 2886 ms 177048 KB Output is correct
4 Correct 2897 ms 179452 KB Output is correct
5 Correct 2817 ms 171928 KB Output is correct
6 Correct 2257 ms 129616 KB Output is correct
7 Correct 3639 ms 206592 KB Output is correct
8 Correct 3687 ms 206704 KB Output is correct
9 Correct 3688 ms 206748 KB Output is correct
10 Correct 3674 ms 206060 KB Output is correct
11 Correct 3654 ms 196132 KB Output is correct
12 Correct 2894 ms 146448 KB Output is correct
13 Correct 3853 ms 220732 KB Output is correct
14 Correct 3729 ms 220872 KB Output is correct
15 Correct 3790 ms 220800 KB Output is correct
16 Correct 3877 ms 220204 KB Output is correct
17 Correct 3681 ms 209460 KB Output is correct
18 Correct 2791 ms 152788 KB Output is correct
19 Correct 3856 ms 220656 KB Output is correct
20 Correct 4194 ms 220700 KB Output is correct
21 Correct 4167 ms 220816 KB Output is correct
22 Correct 4075 ms 219972 KB Output is correct
23 Correct 3772 ms 209520 KB Output is correct
24 Correct 3009 ms 152832 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24524 KB Output is correct
2 Correct 14 ms 24604 KB Output is correct
3 Correct 14 ms 24584 KB Output is correct
4 Correct 14 ms 24524 KB Output is correct
5 Correct 13 ms 24604 KB Output is correct
6 Correct 13 ms 24596 KB Output is correct
7 Correct 13 ms 24524 KB Output is correct
8 Correct 13 ms 24652 KB Output is correct
9 Correct 13 ms 24620 KB Output is correct
10 Correct 15 ms 24524 KB Output is correct
11 Correct 14 ms 24648 KB Output is correct
12 Correct 13 ms 24592 KB Output is correct
13 Correct 13 ms 24576 KB Output is correct
14 Correct 15 ms 24628 KB Output is correct
15 Correct 15 ms 24668 KB Output is correct
16 Correct 15 ms 24668 KB Output is correct
17 Correct 14 ms 24652 KB Output is correct
18 Correct 14 ms 24592 KB Output is correct
19 Correct 31 ms 25488 KB Output is correct
20 Correct 35 ms 25668 KB Output is correct
21 Correct 37 ms 25736 KB Output is correct
22 Correct 38 ms 25860 KB Output is correct
23 Correct 56 ms 29840 KB Output is correct
24 Correct 66 ms 31208 KB Output is correct
25 Correct 72 ms 32068 KB Output is correct
26 Correct 76 ms 33520 KB Output is correct
27 Correct 14 ms 24524 KB Output is correct
28 Correct 13 ms 24576 KB Output is correct
29 Correct 15 ms 24540 KB Output is correct
30 Correct 26 ms 24780 KB Output is correct
31 Correct 73 ms 25716 KB Output is correct
32 Correct 13 ms 24572 KB Output is correct
33 Correct 16 ms 24720 KB Output is correct
34 Correct 14 ms 24820 KB Output is correct
35 Correct 17 ms 24848 KB Output is correct
36 Correct 42 ms 25024 KB Output is correct
37 Correct 129 ms 26020 KB Output is correct
38 Correct 21 ms 26692 KB Output is correct
39 Correct 21 ms 26772 KB Output is correct
40 Correct 26 ms 26816 KB Output is correct
41 Correct 100 ms 27028 KB Output is correct
42 Correct 418 ms 28124 KB Output is correct
43 Correct 185 ms 65072 KB Output is correct
44 Correct 199 ms 65100 KB Output is correct
45 Correct 286 ms 65264 KB Output is correct
46 Correct 1329 ms 65720 KB Output is correct
47 Execution timed out 5032 ms 66568 KB Time limit exceeded
48 Halted 0 ms 0 KB -