Submission #532685

#	Time	Username	Problem	Language	Result	Execution time	Memory
532685		mat50013	Dynamic Diameter (CEOI19_diameter)	C++11	100 / 100	4157 ms	220228 KiB

diameter

#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 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27