Submission #893372

#	Time	Username	Problem	Language	Result	Execution time	Memory
893372		box	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	3542 ms	398704 KiB

wild_boar

#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 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 38 / 38