oj.uz

Submission #779531

# Submission time Handle Problem Language Result Execution time Memory
779531 2023-07-11T13:54:27 Z ThegeekKnight16 Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 378 ms 62648 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f;
struct node
{
    int Mi, Mj, Mk, Mij, Mjk, Mijk;
    int lz;

    node(int I = 0, int J = 0, int K = 0, int IJ = 0, int JK = 0, int IJK = 0, int LZ = 0) : Mi(I), Mj(J), Mk(K), Mij(IJ), Mjk(JK), Mijk(IJK), lz(LZ) {}

    node operator+(node outro)
    {
        node resp;
        resp.Mi = resp.Mk = max(Mi, outro.Mi);
        resp.Mj = min(Mj, outro.Mj);
        resp.Mij = max({Mij, Mi - 2*outro.Mj, outro.Mij});
        resp.Mjk = max({Mjk, -2*Mj + outro.Mk, outro.Mjk});
        resp.Mijk = max({Mijk, Mij + outro.Mk, Mi + outro.Mjk, outro.Mijk});
        return resp;
    }
};
const int MAXN = 2e5 + 10;
array<node, 4*MAXN> seg;
array<vector<pair<int, int>>, MAXN> grafo;
array<int, MAXN> peso, idIn, idOut;
int temp = 0;

void refresh(int pos, int ini, int fim)
{
    if (seg[pos].lz == 0) return;
    int x = seg[pos].lz; seg[pos].lz = 0;
    seg[pos].Mi += x; seg[pos].Mj += x; seg[pos].Mk += x;
    seg[pos].Mij -= x; seg[pos].Mjk -= x;
    seg[pos].Mijk += 0;

    if (ini == fim) return;
    int e = 2*pos; int d = 2*pos + 1;
    seg[e].lz += x;
    seg[d].lz += x;
}

void update(int pos, int ini, int fim, int p, int q, int val)
{
    refresh(pos, ini, fim);
    if (q < ini || p > fim) return;
    if (p <= ini && fim <= q)
    {
        seg[pos].lz += val;
        refresh(pos, ini, fim);
        return;
    }
    int m = (ini + fim) >> 1;
    int e = 2*pos; int d = 2*pos + 1;
    update(e, ini, m, p, q, val);
    update(d, m+1, fim, p, q, val);
    seg[pos] = seg[e] + seg[d];
}

node query(int pos, int ini, int fim, int p, int q)
{
    refresh(pos, ini, fim);
    if (q < ini || p > fim) return node(-INF, INF, -INF, -INF, -INF, -INF);
    if (p <= ini && fim <= q) return seg[pos];
    int m = (ini + fim) >> 1;
    int e = 2*pos; int d = 2*pos + 1;
    return (query(e, ini, m, p, q) + query(d, m+1, fim, p, q));
}

void dfs(int v, int p, int paiEdge)
{
    ++temp;
    if (paiEdge != -1) idIn[paiEdge] = temp;

    for (auto [viz, e] : grafo[v])
    {
        if (viz == p) continue;
        dfs(viz, v, e);
    }

    ++temp;
    if (paiEdge != -1) idOut[paiEdge] = temp;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, Q, W;
    cin >> N >> Q >> W;
    for (int i = 1; i < N; i++)
    {
        int X, Y, P;
        cin >> X >> Y >> P;
        grafo[X].emplace_back(Y, i);
        grafo[Y].emplace_back(X, i);
        peso[i] = P;
    }
    dfs(1, 1, -1);

    --temp;
    for (int i = 1; i < N; i++) update(1, 1, temp, idIn[i], idOut[i]-1, peso[i]);

    // node aux = query(1, 1, temp, 1, temp);
    // cerr << aux.Mi << " " << aux.Mj << " " << aux.Mk << " " << aux.Mij << " " << aux.Mjk << " " << aux.Mijk << '\n';

    int last = 0;
    while (Q--)
    {
        int D, E;
        cin >> D >> E;
        D = (D + last) % (N - 1); ++D;
        E = (E + last) % W;
        update(1, 1, temp, idIn[D], idOut[D]-1, E - peso[D]);
        peso[D] = E;
        last = query(1, 1, temp, 1, temp).Mijk;
        cout << last << '\n';
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 48852 KB Output is correct
2 Correct 17 ms 48852 KB Output is correct
3 Correct 18 ms 48764 KB Output is correct
4 Correct 21 ms 48796 KB Output is correct
5 Correct 17 ms 48816 KB Output is correct
6 Correct 17 ms 48776 KB Output is correct
7 Correct 19 ms 48836 KB Output is correct
8 Correct 18 ms 48760 KB Output is correct
9 Correct 17 ms 48860 KB Output is correct
10 Correct 18 ms 48844 KB Output is correct
11 Correct 18 ms 48852 KB Output is correct
12 Correct 17 ms 48860 KB Output is correct
13 Correct 18 ms 48856 KB Output is correct
14 Correct 18 ms 48852 KB Output is correct
15 Correct 18 ms 48852 KB Output is correct
16 Correct 18 ms 48764 KB Output is correct
17 Correct 18 ms 48852 KB Output is correct
18 Correct 18 ms 48812 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 48852 KB Output is correct
2 Correct 17 ms 48852 KB Output is correct
3 Correct 18 ms 48764 KB Output is correct
4 Correct 21 ms 48796 KB Output is correct
5 Correct 17 ms 48816 KB Output is correct
6 Correct 17 ms 48776 KB Output is correct
7 Correct 19 ms 48836 KB Output is correct
8 Correct 18 ms 48760 KB Output is correct
9 Correct 17 ms 48860 KB Output is correct
10 Correct 18 ms 48844 KB Output is correct
11 Correct 18 ms 48852 KB Output is correct
12 Correct 17 ms 48860 KB Output is correct
13 Correct 18 ms 48856 KB Output is correct
14 Correct 18 ms 48852 KB Output is correct
15 Correct 18 ms 48852 KB Output is correct
16 Correct 18 ms 48764 KB Output is correct
17 Correct 18 ms 48852 KB Output is correct
18 Correct 18 ms 48812 KB Output is correct
19 Correct 20 ms 48940 KB Output is correct
20 Correct 21 ms 48952 KB Output is correct
21 Correct 21 ms 48996 KB Output is correct
22 Correct 21 ms 48988 KB Output is correct
23 Correct 27 ms 49316 KB Output is correct
24 Correct 24 ms 49356 KB Output is correct
25 Correct 25 ms 49436 KB Output is correct
26 Correct 27 ms 49652 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 48836 KB Output is correct
2 Correct 18 ms 48832 KB Output is correct
3 Correct 17 ms 48864 KB Output is correct
4 Correct 23 ms 49108 KB Output is correct
5 Correct 46 ms 49796 KB Output is correct
6 Correct 18 ms 48852 KB Output is correct
7 Correct 18 ms 48852 KB Output is correct
8 Correct 19 ms 48852 KB Output is correct
9 Correct 19 ms 48844 KB Output is correct
10 Correct 28 ms 49144 KB Output is correct
11 Correct 53 ms 49796 KB Output is correct
12 Correct 20 ms 49236 KB Output is correct
13 Correct 20 ms 49236 KB Output is correct
14 Correct 21 ms 49260 KB Output is correct
15 Correct 33 ms 49512 KB Output is correct
16 Correct 63 ms 50168 KB Output is correct
17 Correct 65 ms 56324 KB Output is correct
18 Correct 68 ms 56472 KB Output is correct
19 Correct 66 ms 56412 KB Output is correct
20 Correct 77 ms 56648 KB Output is correct
21 Correct 131 ms 57064 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 48908 KB Output is correct
2 Correct 23 ms 49064 KB Output is correct
3 Correct 43 ms 49524 KB Output is correct
4 Correct 67 ms 50096 KB Output is correct
5 Correct 26 ms 49800 KB Output is correct
6 Correct 31 ms 49872 KB Output is correct
7 Correct 56 ms 50452 KB Output is correct
8 Correct 94 ms 50872 KB Output is correct
9 Correct 50 ms 53024 KB Output is correct
10 Correct 58 ms 53072 KB Output is correct
11 Correct 86 ms 53316 KB Output is correct
12 Correct 129 ms 53288 KB Output is correct
13 Correct 84 ms 56664 KB Output is correct
14 Correct 93 ms 56712 KB Output is correct
15 Correct 127 ms 56876 KB Output is correct
16 Correct 181 ms 57216 KB Output is correct
17 Correct 144 ms 57212 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 57952 KB Output is correct
2 Correct 223 ms 57956 KB Output is correct
3 Correct 219 ms 57932 KB Output is correct
4 Correct 220 ms 57844 KB Output is correct
5 Correct 209 ms 57740 KB Output is correct
6 Correct 176 ms 57544 KB Output is correct
7 Correct 255 ms 59728 KB Output is correct
8 Correct 267 ms 59900 KB Output is correct
9 Correct 263 ms 59732 KB Output is correct
10 Correct 254 ms 59724 KB Output is correct
11 Correct 299 ms 59628 KB Output is correct
12 Correct 214 ms 58800 KB Output is correct
13 Correct 369 ms 62564 KB Output is correct
14 Correct 308 ms 62648 KB Output is correct
15 Correct 333 ms 62556 KB Output is correct
16 Correct 338 ms 62564 KB Output is correct
17 Correct 365 ms 62120 KB Output is correct
18 Correct 263 ms 59892 KB Output is correct
19 Correct 310 ms 62552 KB Output is correct
20 Correct 304 ms 62536 KB Output is correct
21 Correct 345 ms 62640 KB Output is correct
22 Correct 346 ms 62508 KB Output is correct
23 Correct 299 ms 62128 KB Output is correct
24 Correct 273 ms 59912 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 48852 KB Output is correct
2 Correct 17 ms 48852 KB Output is correct
3 Correct 18 ms 48764 KB Output is correct
4 Correct 21 ms 48796 KB Output is correct
5 Correct 17 ms 48816 KB Output is correct
6 Correct 17 ms 48776 KB Output is correct
7 Correct 19 ms 48836 KB Output is correct
8 Correct 18 ms 48760 KB Output is correct
9 Correct 17 ms 48860 KB Output is correct
10 Correct 18 ms 48844 KB Output is correct
11 Correct 18 ms 48852 KB Output is correct
12 Correct 17 ms 48860 KB Output is correct
13 Correct 18 ms 48856 KB Output is correct
14 Correct 18 ms 48852 KB Output is correct
15 Correct 18 ms 48852 KB Output is correct
16 Correct 18 ms 48764 KB Output is correct
17 Correct 18 ms 48852 KB Output is correct
18 Correct 18 ms 48812 KB Output is correct
19 Correct 20 ms 48940 KB Output is correct
20 Correct 21 ms 48952 KB Output is correct
21 Correct 21 ms 48996 KB Output is correct
22 Correct 21 ms 48988 KB Output is correct
23 Correct 27 ms 49316 KB Output is correct
24 Correct 24 ms 49356 KB Output is correct
25 Correct 25 ms 49436 KB Output is correct
26 Correct 27 ms 49652 KB Output is correct
27 Correct 18 ms 48836 KB Output is correct
28 Correct 18 ms 48832 KB Output is correct
29 Correct 17 ms 48864 KB Output is correct
30 Correct 23 ms 49108 KB Output is correct
31 Correct 46 ms 49796 KB Output is correct
32 Correct 18 ms 48852 KB Output is correct
33 Correct 18 ms 48852 KB Output is correct
34 Correct 19 ms 48852 KB Output is correct
35 Correct 19 ms 48844 KB Output is correct
36 Correct 28 ms 49144 KB Output is correct
37 Correct 53 ms 49796 KB Output is correct
38 Correct 20 ms 49236 KB Output is correct
39 Correct 20 ms 49236 KB Output is correct
40 Correct 21 ms 49260 KB Output is correct
41 Correct 33 ms 49512 KB Output is correct
42 Correct 63 ms 50168 KB Output is correct
43 Correct 65 ms 56324 KB Output is correct
44 Correct 68 ms 56472 KB Output is correct
45 Correct 66 ms 56412 KB Output is correct
46 Correct 77 ms 56648 KB Output is correct
47 Correct 131 ms 57064 KB Output is correct
48 Correct 19 ms 48908 KB Output is correct
49 Correct 23 ms 49064 KB Output is correct
50 Correct 43 ms 49524 KB Output is correct
51 Correct 67 ms 50096 KB Output is correct
52 Correct 26 ms 49800 KB Output is correct
53 Correct 31 ms 49872 KB Output is correct
54 Correct 56 ms 50452 KB Output is correct
55 Correct 94 ms 50872 KB Output is correct
56 Correct 50 ms 53024 KB Output is correct
57 Correct 58 ms 53072 KB Output is correct
58 Correct 86 ms 53316 KB Output is correct
59 Correct 129 ms 53288 KB Output is correct
60 Correct 84 ms 56664 KB Output is correct
61 Correct 93 ms 56712 KB Output is correct
62 Correct 127 ms 56876 KB Output is correct
63 Correct 181 ms 57216 KB Output is correct
64 Correct 144 ms 57212 KB Output is correct
65 Correct 233 ms 57952 KB Output is correct
66 Correct 223 ms 57956 KB Output is correct
67 Correct 219 ms 57932 KB Output is correct
68 Correct 220 ms 57844 KB Output is correct
69 Correct 209 ms 57740 KB Output is correct
70 Correct 176 ms 57544 KB Output is correct
71 Correct 255 ms 59728 KB Output is correct
72 Correct 267 ms 59900 KB Output is correct
73 Correct 263 ms 59732 KB Output is correct
74 Correct 254 ms 59724 KB Output is correct
75 Correct 299 ms 59628 KB Output is correct
76 Correct 214 ms 58800 KB Output is correct
77 Correct 369 ms 62564 KB Output is correct
78 Correct 308 ms 62648 KB Output is correct
79 Correct 333 ms 62556 KB Output is correct
80 Correct 338 ms 62564 KB Output is correct
81 Correct 365 ms 62120 KB Output is correct
82 Correct 263 ms 59892 KB Output is correct
83 Correct 310 ms 62552 KB Output is correct
84 Correct 304 ms 62536 KB Output is correct
85 Correct 345 ms 62640 KB Output is correct
86 Correct 346 ms 62508 KB Output is correct
87 Correct 299 ms 62128 KB Output is correct
88 Correct 273 ms 59912 KB Output is correct
89 Correct 208 ms 57604 KB Output is correct
90 Correct 221 ms 57804 KB Output is correct
91 Correct 268 ms 58908 KB Output is correct
92 Correct 250 ms 58864 KB Output is correct
93 Correct 305 ms 60684 KB Output is correct
94 Correct 347 ms 60072 KB Output is correct
95 Correct 378 ms 61124 KB Output is correct
96 Correct 292 ms 60372 KB Output is correct
97 Correct 330 ms 61068 KB Output is correct
98 Correct 361 ms 62396 KB Output is correct
99 Correct 328 ms 60812 KB Output is correct
100 Correct 329 ms 60892 KB Output is correct