oj.uz

Submission #893372

# Submission time Handle Problem Language Result Execution time Memory
893372 2023-12-27T03:36:03 Z box Wild Boar (JOI18_wild_boar) C++17
100 / 100
 3542 ms 398704 KB 
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int MAXN = 2e3, MAXM = 4e3, MAXL = 1e5;
const i64 INF = 1e18;

int N, M, T, L;

struct edge {
    int s, t, w;
} edge[MAXM];

vector<int> from[MAXN];
i64 dist[MAXM][MAXM];
list<int> undone[MAXN];

struct info {
    ar<int, 4> S, T; ar<i64, 4> W;
    info() {
        for (int i = 0; i < 4; i++) S[i] = T[i] = -1, W[i] = INF;
    }
    void set(int i, int s, int t, i64 w) {
        S[i] = s, T[i] = t, W[i] = w;
    }
    void pul(const info &a, const info &b) {
        for (int i = 0; i < 4; i++) S[i] = T[i] = -1, W[i] = INF;
        for (int x = 0; x < 4; x++) for (int y = 0; y < 4; y++) if ((a.T[x] ^ b.S[y] ^ 1) && a.W[x] + b.W[y] < W[0])
            set(0, a.S[x], b.T[y], a.W[x] + b.W[y]);
        for (int x = 0; x < 4; x++) for (int y = 0; y < 4; y++) if ((a.T[x] ^ b.S[y] ^ 1) && a.W[x] + b.W[y] < W[1] && (a.S[x] ^ S[0]) && (b.T[y] ^ T[0]))
            set(1, a.S[x], b.T[y], a.W[x] + b.W[y]);
        for (int x = 0; x < 4; x++) for (int y = 0; y < 4; y++) if ((a.T[x] ^ b.S[y] ^ 1) && a.W[x] + b.W[y] < W[2] && (a.S[x] ^ S[0]) && (b.T[y] ^ T[1]))
            set(2, a.S[x], b.T[y], a.W[x] + b.W[y]);
        for (int x = 0; x < 4; x++) for (int y = 0; y < 4; y++) if ((a.T[x] ^ b.S[y] ^ 1) && a.W[x] + b.W[y] < W[3] && (a.S[x] ^ S[1]) && (b.T[y] ^ T[0]))
            set(3, a.S[x], b.T[y], a.W[x] + b.W[y]);
    }
} memo[MAXN][MAXN], t;

int perm[MAXL];

struct tree {
    int l, r;
    tree *lc = NULL, *rc = NULL;
    info x;
    tree(int l, int r) : l(l), r(r) {
        if (l < r) {
            int m = (l + r) / 2;
            lc = new tree(l, m);
            rc = new tree(m + 1, r);
            x.pul(lc->x, rc->x);
        } else x = memo[perm[l]][perm[l + 1]];
    }
    void upd(int i) {
        if (l == r) {
            x = memo[perm[l]][perm[l + 1]];
        } else {
            i <= lc->r ? lc->upd(i) : rc->upd(i);
            x.pul(lc->x, rc->x);
        }
    }
    i64 qry() {
        return x.W[0];
    }
} *tr;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M >> T >> L;
    for (int h = 0; h < M; h++) {
        int i, j, w;
        cin >> i >> j >> w, i--, j--;
        edge[h * 2] = {i, j, w};
        edge[h * 2 + 1] = {j, i, w};
        from[i].push_back(h * 2);
        from[j].push_back(h * 2 + 1);
    }
    for (int x = 0; x < M * 2; x++) {
        fill(dist[x], dist[x] + M * 2, INF);
        for (int i = 0; i < N; i++) exchange(undone[i], {});
        for (int h = 0; h < M * 2; h++) undone[edge[h].s].push_back(h);
        priority_queue<pair<i64, int>> qu;
        dist[x][x] = edge[x].w;
        qu.push({-dist[x][x], x});
        while (sz(qu)) {
            auto [d, i] = qu.top(); qu.pop();
            d *= -1;
            if (dist[x][i] != d) continue;
            for (auto j = begin(undone[edge[i].t]); j != end(undone[edge[i].t]); )
                if (*j ^ i ^ 1) {
                    if (dist[x][i] + edge[*j].w < dist[x][*j]) {
                        dist[x][*j] = dist[x][i] + edge[*j].w;
                        qu.push({-dist[x][*j], *j});
                    }
                    auto p = j++;
                    undone[edge[i].t].erase(p);
                } else ++j;
        }
    }
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        for (int x : from[i]) for (int y : from[j]) if (dist[x][y ^ 1] < t.W[0])
            t.set(0, x, y ^ 1, dist[x][y ^ 1]);
        for (int x : from[i]) for (int y : from[j]) if (dist[x][y ^ 1] < t.W[1] && (x ^ t.S[0]) && (y ^ t.T[0] ^ 1))
            t.set(1, x, y ^ 1, dist[x][y ^ 1]);
        for (int x : from[i]) for (int y : from[j]) if (dist[x][y ^ 1] < t.W[2] && (x ^ t.S[0]) && (y ^ t.T[1] ^ 1))
            t.set(2, x, y ^ 1, dist[x][y ^ 1]);
        for (int x : from[i]) for (int y : from[j]) if (dist[x][y ^ 1] < t.W[3] && (x ^ t.S[1]) && (y ^ t.T[0] ^ 1))
            t.set(3, x, y ^ 1, dist[x][y ^ 1]);
        swap(memo[i][j], t);
    }
    for (int i = 0; i < L; i++) cin >> perm[i], perm[i]--;
    tr = new tree(0, L - 2);
    while (T--) {
        int i, v;
        cin >> i >> v, i--, v--;
        perm[i] = v;
        if (i) tr->upd(i - 1);
        if (i < L - 1) tr->upd(i);
        i64 x = tr->qry();
        cout << (x == INF ? -1 : x) << endl;
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 252748 KB Output is correct
2 Correct 40 ms 252696 KB Output is correct
3 Correct 39 ms 252748 KB Output is correct
4 Correct 40 ms 252752 KB Output is correct
5 Correct 40 ms 252756 KB Output is correct
6 Correct 39 ms 252760 KB Output is correct
7 Correct 43 ms 252848 KB Output is correct
8 Correct 41 ms 252756 KB Output is correct
9 Correct 41 ms 252752 KB Output is correct
10 Correct 44 ms 252756 KB Output is correct
11 Correct 40 ms 252900 KB Output is correct
12 Correct 40 ms 252756 KB Output is correct
13 Correct 40 ms 252744 KB Output is correct
14 Correct 39 ms 252764 KB Output is correct
15 Correct 40 ms 252752 KB Output is correct
16 Correct 45 ms 252756 KB Output is correct
17 Correct 41 ms 252752 KB Output is correct
18 Correct 39 ms 252736 KB Output is correct
19 Correct 40 ms 252756 KB Output is correct
20 Correct 39 ms 252756 KB Output is correct
21 Correct 39 ms 252888 KB Output is correct
22 Correct 39 ms 252752 KB Output is correct
23 Correct 39 ms 252752 KB Output is correct
24 Correct 41 ms 252704 KB Output is correct
25 Correct 39 ms 252756 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 252748 KB Output is correct
2 Correct 40 ms 252696 KB Output is correct
3 Correct 39 ms 252748 KB Output is correct
4 Correct 40 ms 252752 KB Output is correct
5 Correct 40 ms 252756 KB Output is correct
6 Correct 39 ms 252760 KB Output is correct
7 Correct 43 ms 252848 KB Output is correct
8 Correct 41 ms 252756 KB Output is correct
9 Correct 41 ms 252752 KB Output is correct
10 Correct 44 ms 252756 KB Output is correct
11 Correct 40 ms 252900 KB Output is correct
12 Correct 40 ms 252756 KB Output is correct
13 Correct 40 ms 252744 KB Output is correct
14 Correct 39 ms 252764 KB Output is correct
15 Correct 40 ms 252752 KB Output is correct
16 Correct 45 ms 252756 KB Output is correct
17 Correct 41 ms 252752 KB Output is correct
18 Correct 39 ms 252736 KB Output is correct
19 Correct 40 ms 252756 KB Output is correct
20 Correct 39 ms 252756 KB Output is correct
21 Correct 39 ms 252888 KB Output is correct
22 Correct 39 ms 252752 KB Output is correct
23 Correct 39 ms 252752 KB Output is correct
24 Correct 41 ms 252704 KB Output is correct
25 Correct 39 ms 252756 KB Output is correct
26 Correct 41 ms 254804 KB Output is correct
27 Correct 71 ms 278356 KB Output is correct
28 Correct 64 ms 278096 KB Output is correct
29 Correct 135 ms 290596 KB Output is correct
30 Correct 126 ms 290388 KB Output is correct
31 Correct 123 ms 290620 KB Output is correct
32 Correct 118 ms 290384 KB Output is correct
33 Correct 132 ms 290644 KB Output is correct
34 Correct 132 ms 290644 KB Output is correct
35 Correct 117 ms 290468 KB Output is correct
36 Correct 120 ms 290384 KB Output is correct
37 Correct 137 ms 290516 KB Output is correct
38 Correct 129 ms 290640 KB Output is correct
39 Correct 118 ms 290388 KB Output is correct
40 Correct 131 ms 290608 KB Output is correct
41 Correct 130 ms 290604 KB Output is correct
42 Correct 110 ms 290384 KB Output is correct
43 Correct 128 ms 290844 KB Output is correct
44 Correct 122 ms 290608 KB Output is correct
45 Correct 88 ms 290648 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 252748 KB Output is correct
2 Correct 40 ms 252696 KB Output is correct
3 Correct 39 ms 252748 KB Output is correct
4 Correct 40 ms 252752 KB Output is correct
5 Correct 40 ms 252756 KB Output is correct
6 Correct 39 ms 252760 KB Output is correct
7 Correct 43 ms 252848 KB Output is correct
8 Correct 41 ms 252756 KB Output is correct
9 Correct 41 ms 252752 KB Output is correct
10 Correct 44 ms 252756 KB Output is correct
11 Correct 40 ms 252900 KB Output is correct
12 Correct 40 ms 252756 KB Output is correct
13 Correct 40 ms 252744 KB Output is correct
14 Correct 39 ms 252764 KB Output is correct
15 Correct 40 ms 252752 KB Output is correct
16 Correct 45 ms 252756 KB Output is correct
17 Correct 41 ms 252752 KB Output is correct
18 Correct 39 ms 252736 KB Output is correct
19 Correct 40 ms 252756 KB Output is correct
20 Correct 39 ms 252756 KB Output is correct
21 Correct 39 ms 252888 KB Output is correct
22 Correct 39 ms 252752 KB Output is correct
23 Correct 39 ms 252752 KB Output is correct
24 Correct 41 ms 252704 KB Output is correct
25 Correct 39 ms 252756 KB Output is correct
26 Correct 41 ms 254804 KB Output is correct
27 Correct 71 ms 278356 KB Output is correct
28 Correct 64 ms 278096 KB Output is correct
29 Correct 135 ms 290596 KB Output is correct
30 Correct 126 ms 290388 KB Output is correct
31 Correct 123 ms 290620 KB Output is correct
32 Correct 118 ms 290384 KB Output is correct
33 Correct 132 ms 290644 KB Output is correct
34 Correct 132 ms 290644 KB Output is correct
35 Correct 117 ms 290468 KB Output is correct
36 Correct 120 ms 290384 KB Output is correct
37 Correct 137 ms 290516 KB Output is correct
38 Correct 129 ms 290640 KB Output is correct
39 Correct 118 ms 290388 KB Output is correct
40 Correct 131 ms 290608 KB Output is correct
41 Correct 130 ms 290604 KB Output is correct
42 Correct 110 ms 290384 KB Output is correct
43 Correct 128 ms 290844 KB Output is correct
44 Correct 122 ms 290608 KB Output is correct
45 Correct 88 ms 290648 KB Output is correct
46 Correct 184 ms 283692 KB Output is correct
47 Correct 2503 ms 395668 KB Output is correct
48 Correct 2569 ms 395712 KB Output is correct
49 Correct 2624 ms 395516 KB Output is correct
50 Correct 2578 ms 395584 KB Output is correct
51 Correct 2637 ms 395580 KB Output is correct
52 Correct 2808 ms 395816 KB Output is correct
53 Correct 2805 ms 395812 KB Output is correct
54 Correct 2734 ms 396240 KB Output is correct
55 Correct 2724 ms 396228 KB Output is correct
56 Correct 2738 ms 396048 KB Output is correct
57 Correct 2557 ms 396048 KB Output is correct
58 Correct 2685 ms 395840 KB Output is correct
59 Correct 2378 ms 395752 KB Output is correct
60 Correct 2331 ms 395960 KB Output is correct
61 Correct 2313 ms 395884 KB Output is correct
62 Correct 2148 ms 395980 KB Output is correct
63 Correct 2101 ms 396112 KB Output is correct
64 Correct 778 ms 396152 KB Output is correct
65 Correct 789 ms 396244 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 252748 KB Output is correct
2 Correct 40 ms 252696 KB Output is correct
3 Correct 39 ms 252748 KB Output is correct
4 Correct 40 ms 252752 KB Output is correct
5 Correct 40 ms 252756 KB Output is correct
6 Correct 39 ms 252760 KB Output is correct
7 Correct 43 ms 252848 KB Output is correct
8 Correct 41 ms 252756 KB Output is correct
9 Correct 41 ms 252752 KB Output is correct
10 Correct 44 ms 252756 KB Output is correct
11 Correct 40 ms 252900 KB Output is correct
12 Correct 40 ms 252756 KB Output is correct
13 Correct 40 ms 252744 KB Output is correct
14 Correct 39 ms 252764 KB Output is correct
15 Correct 40 ms 252752 KB Output is correct
16 Correct 45 ms 252756 KB Output is correct
17 Correct 41 ms 252752 KB Output is correct
18 Correct 39 ms 252736 KB Output is correct
19 Correct 40 ms 252756 KB Output is correct
20 Correct 39 ms 252756 KB Output is correct
21 Correct 39 ms 252888 KB Output is correct
22 Correct 39 ms 252752 KB Output is correct
23 Correct 39 ms 252752 KB Output is correct
24 Correct 41 ms 252704 KB Output is correct
25 Correct 39 ms 252756 KB Output is correct
26 Correct 41 ms 254804 KB Output is correct
27 Correct 71 ms 278356 KB Output is correct
28 Correct 64 ms 278096 KB Output is correct
29 Correct 135 ms 290596 KB Output is correct
30 Correct 126 ms 290388 KB Output is correct
31 Correct 123 ms 290620 KB Output is correct
32 Correct 118 ms 290384 KB Output is correct
33 Correct 132 ms 290644 KB Output is correct
34 Correct 132 ms 290644 KB Output is correct
35 Correct 117 ms 290468 KB Output is correct
36 Correct 120 ms 290384 KB Output is correct
37 Correct 137 ms 290516 KB Output is correct
38 Correct 129 ms 290640 KB Output is correct
39 Correct 118 ms 290388 KB Output is correct
40 Correct 131 ms 290608 KB Output is correct
41 Correct 130 ms 290604 KB Output is correct
42 Correct 110 ms 290384 KB Output is correct
43 Correct 128 ms 290844 KB Output is correct
44 Correct 122 ms 290608 KB Output is correct
45 Correct 88 ms 290648 KB Output is correct
46 Correct 184 ms 283692 KB Output is correct
47 Correct 2503 ms 395668 KB Output is correct
48 Correct 2569 ms 395712 KB Output is correct
49 Correct 2624 ms 395516 KB Output is correct
50 Correct 2578 ms 395584 KB Output is correct
51 Correct 2637 ms 395580 KB Output is correct
52 Correct 2808 ms 395816 KB Output is correct
53 Correct 2805 ms 395812 KB Output is correct
54 Correct 2734 ms 396240 KB Output is correct
55 Correct 2724 ms 396228 KB Output is correct
56 Correct 2738 ms 396048 KB Output is correct
57 Correct 2557 ms 396048 KB Output is correct
58 Correct 2685 ms 395840 KB Output is correct
59 Correct 2378 ms 395752 KB Output is correct
60 Correct 2331 ms 395960 KB Output is correct
61 Correct 2313 ms 395884 KB Output is correct
62 Correct 2148 ms 395980 KB Output is correct
63 Correct 2101 ms 396112 KB Output is correct
64 Correct 778 ms 396152 KB Output is correct
65 Correct 789 ms 396244 KB Output is correct
66 Correct 80 ms 274004 KB Output is correct
67 Correct 515 ms 315984 KB Output is correct
68 Correct 915 ms 376772 KB Output is correct
69 Correct 1182 ms 377796 KB Output is correct
70 Correct 1390 ms 397364 KB Output is correct
71 Correct 3221 ms 398160 KB Output is correct
72 Correct 3285 ms 397704 KB Output is correct
73 Correct 3528 ms 398496 KB Output is correct
74 Correct 3501 ms 398288 KB Output is correct
75 Correct 3521 ms 398460 KB Output is correct
76 Correct 3247 ms 398152 KB Output is correct
77 Correct 3139 ms 397840 KB Output is correct
78 Correct 2881 ms 397884 KB Output is correct
79 Correct 3365 ms 398468 KB Output is correct
80 Correct 3542 ms 398604 KB Output is correct
81 Correct 3051 ms 397948 KB Output is correct
82 Correct 3170 ms 398588 KB Output is correct
83 Correct 2828 ms 398016 KB Output is correct
84 Correct 2811 ms 398604 KB Output is correct
85 Correct 1412 ms 398704 KB Output is correct