oj.uz

Submission #532658

# Submission time Handle Problem Language Result Execution time Memory
532658 2022-03-03T14:56:02 Z mat50013 Dynamic Diameter (CEOI19_diameter) C++11
42 / 100
 5000 ms 158956 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];
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]);
}

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)
    {
        vector<ll> vec;
        for(auto it: frati[i])
        {
            ll val = interv[i].query(1, 1, interv[i].cati, interv[i].in[it], interv[i].out[it]);
            vec.push_back(val);
        }
        sort(vec.begin(), vec.end(), greater<ll>());
        ll maxxx = 0;
        if(vec.size() > 1)
            maxxx = vec[0] + vec[1];
        else maxxx = vec[0];
        return maxxx;
    };

    multiset<ll> s;
    for(int i = 1; i <= n; ++i)
        if(frati[i].size())
            maxx[i] = calc(i), 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);
            s.erase(s.find(-maxx[it.second]));
            maxx[it.second] = calc(it.second);
            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 12 ms 15180 KB Output is correct
2 Correct 9 ms 15180 KB Output is correct
3 Correct 10 ms 15180 KB Output is correct
4 Correct 11 ms 15180 KB Output is correct
5 Correct 10 ms 15200 KB Output is correct
6 Correct 9 ms 15180 KB Output is correct
7 Correct 9 ms 15156 KB Output is correct
8 Correct 9 ms 15180 KB Output is correct
9 Correct 8 ms 15180 KB Output is correct
10 Correct 8 ms 15180 KB Output is correct
11 Correct 7 ms 15212 KB Output is correct
12 Correct 8 ms 15180 KB Output is correct
13 Correct 9 ms 15180 KB Output is correct
14 Correct 9 ms 15272 KB Output is correct
15 Correct 8 ms 15180 KB Output is correct
16 Correct 8 ms 15180 KB Output is correct
17 Correct 8 ms 15292 KB Output is correct
18 Correct 9 ms 15180 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15180 KB Output is correct
2 Correct 9 ms 15180 KB Output is correct
3 Correct 10 ms 15180 KB Output is correct
4 Correct 11 ms 15180 KB Output is correct
5 Correct 10 ms 15200 KB Output is correct
6 Correct 9 ms 15180 KB Output is correct
7 Correct 9 ms 15156 KB Output is correct
8 Correct 9 ms 15180 KB Output is correct
9 Correct 8 ms 15180 KB Output is correct
10 Correct 8 ms 15180 KB Output is correct
11 Correct 7 ms 15212 KB Output is correct
12 Correct 8 ms 15180 KB Output is correct
13 Correct 9 ms 15180 KB Output is correct
14 Correct 9 ms 15272 KB Output is correct
15 Correct 8 ms 15180 KB Output is correct
16 Correct 8 ms 15180 KB Output is correct
17 Correct 8 ms 15292 KB Output is correct
18 Correct 9 ms 15180 KB Output is correct
19 Correct 48 ms 16032 KB Output is correct
20 Correct 37 ms 16120 KB Output is correct
21 Correct 40 ms 16152 KB Output is correct
22 Correct 33 ms 16260 KB Output is correct
23 Correct 66 ms 19880 KB Output is correct
24 Correct 67 ms 21068 KB Output is correct
25 Correct 74 ms 22028 KB Output is correct
26 Correct 73 ms 23384 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15180 KB Output is correct
2 Correct 11 ms 15180 KB Output is correct
3 Correct 14 ms 15228 KB Output is correct
4 Correct 36 ms 15300 KB Output is correct
5 Correct 137 ms 15528 KB Output is correct
6 Correct 8 ms 15180 KB Output is correct
7 Correct 10 ms 15364 KB Output is correct
8 Correct 18 ms 15308 KB Output is correct
9 Correct 108 ms 15388 KB Output is correct
10 Correct 976 ms 15580 KB Output is correct
11 Correct 4764 ms 15900 KB Output is correct
12 Correct 26 ms 16972 KB Output is correct
13 Correct 172 ms 17064 KB Output is correct
14 Correct 1381 ms 17204 KB Output is correct
15 Execution timed out 5087 ms 17060 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16076 KB Output is correct
2 Correct 40 ms 16088 KB Output is correct
3 Correct 157 ms 16336 KB Output is correct
4 Correct 318 ms 16664 KB Output is correct
5 Correct 61 ms 27072 KB Output is correct
6 Correct 94 ms 27144 KB Output is correct
7 Correct 308 ms 27404 KB Output is correct
8 Correct 596 ms 27712 KB Output is correct
9 Correct 203 ms 81332 KB Output is correct
10 Correct 304 ms 81492 KB Output is correct
11 Correct 688 ms 81524 KB Output is correct
12 Correct 1155 ms 82068 KB Output is correct
13 Correct 442 ms 155352 KB Output is correct
14 Correct 527 ms 155480 KB Output is correct
15 Correct 989 ms 156148 KB Output is correct
16 Correct 1625 ms 156944 KB Output is correct
17 Correct 2560 ms 156724 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3421 ms 151128 KB Output is correct
2 Correct 3437 ms 158060 KB Output is correct
3 Correct 3428 ms 156544 KB Output is correct
4 Correct 3551 ms 158956 KB Output is correct
5 Execution timed out 5059 ms 151640 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15180 KB Output is correct
2 Correct 9 ms 15180 KB Output is correct
3 Correct 10 ms 15180 KB Output is correct
4 Correct 11 ms 15180 KB Output is correct
5 Correct 10 ms 15200 KB Output is correct
6 Correct 9 ms 15180 KB Output is correct
7 Correct 9 ms 15156 KB Output is correct
8 Correct 9 ms 15180 KB Output is correct
9 Correct 8 ms 15180 KB Output is correct
10 Correct 8 ms 15180 KB Output is correct
11 Correct 7 ms 15212 KB Output is correct
12 Correct 8 ms 15180 KB Output is correct
13 Correct 9 ms 15180 KB Output is correct
14 Correct 9 ms 15272 KB Output is correct
15 Correct 8 ms 15180 KB Output is correct
16 Correct 8 ms 15180 KB Output is correct
17 Correct 8 ms 15292 KB Output is correct
18 Correct 9 ms 15180 KB Output is correct
19 Correct 48 ms 16032 KB Output is correct
20 Correct 37 ms 16120 KB Output is correct
21 Correct 40 ms 16152 KB Output is correct
22 Correct 33 ms 16260 KB Output is correct
23 Correct 66 ms 19880 KB Output is correct
24 Correct 67 ms 21068 KB Output is correct
25 Correct 74 ms 22028 KB Output is correct
26 Correct 73 ms 23384 KB Output is correct
27 Correct 11 ms 15180 KB Output is correct
28 Correct 11 ms 15180 KB Output is correct
29 Correct 14 ms 15228 KB Output is correct
30 Correct 36 ms 15300 KB Output is correct
31 Correct 137 ms 15528 KB Output is correct
32 Correct 8 ms 15180 KB Output is correct
33 Correct 10 ms 15364 KB Output is correct
34 Correct 18 ms 15308 KB Output is correct
35 Correct 108 ms 15388 KB Output is correct
36 Correct 976 ms 15580 KB Output is correct
37 Correct 4764 ms 15900 KB Output is correct
38 Correct 26 ms 16972 KB Output is correct
39 Correct 172 ms 17064 KB Output is correct
40 Correct 1381 ms 17204 KB Output is correct
41 Execution timed out 5087 ms 17060 KB Time limit exceeded
42 Halted 0 ms 0 KB -