Submission #380289

#	Time	Username	Problem	Language	Result	Execution time	Memory
380289		fishy15	Wild Boar (JOI18_wild_boar)	C++17	0 / 100	18079 ms	72428 KiB

wild_boar

#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>

#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

// change if necessary
#define MAXN 1010
#define MAXL 100010

using namespace std;

struct path {
    int start, end;
    ll length;

    path(int s, int e, ll l) : start(s), end(e), length(l) {}
    path() : path(0, 0, 0) {}
};

struct min_cost {
    path min[4]; // min, first diff, second diff, both diff
    bool set[4];

    min_cost() { memset(set, 0, sizeof set); }
};

int n, m, t, l;
int nums[MAXL];
min_cost min_dist[MAXN][MAXN];
vector<int> adj[MAXN];
vector<pair<int, ll>> edge;

bool same(int x, int y) {
    return x == y || (x ^ 1) == y;
}

// segtree stuff
struct segtree {
    struct node {
        int l, r, sz;
        vector<path> combo;

        node(int l, int r, int sz) : l(l), r(r), sz(sz) {}
        node() : node(0, 0, 0) {}
        int size() const { return r - l + 1; }
    };

    static int n;
    node st[4 * MAXN];

    // i have no clue why this works but if i set T = path[4]
    // then it is passed as a pointer instead of an array
    // so i am doing this instead
    template<class T>
    void combo(node &ans, const vector<path> &left, const T &right) {
        map<pair<int, int>, ll> m;
        for (auto &p1 : left) {
            for (auto &p2 : right) {
                if (same(p1.end, p2.start) || p2.length == 0) continue;
                pair<int, int> pp = {p1.start, p2.end};
                if (!m.count(pp)) {
                    m[pp] = p1.length + p2.length;
                } else {
                    m[pp] = min(m[pp], p1.length + p2.length);
                }
            }
        }

        for (auto p : m) {
            ans.combo.emplace_back(p.first.first, p.first.second, p.second);
        }
    }

    void combo(node &ans, const vector<path> &left, const vector<path> &right, int x1, int x2) {
        map<pair<int, int>, ll> m;
        for (auto &p1 : left) {
            for (auto &p2 : right) {
                for (auto &join : min_dist[x1][x2].min) {
                    if (same(p1.end, join.start) || same(join.end, p2.start) || join.length == 0) continue;
                    pair<int, int> pp = {p1.start, p2.end};
                    if (!m.count(pp)) {
                        m[pp] = p1.length + p2.length + join.length;
                    } else {
                        m[pp] = min(m[pp], p1.length + p2.length + join.length);
                    }
                }
            }
        }

        for (auto p : m) {
            ans.combo.emplace_back(p.first.first, p.first.second, p.second);
        }
    }

    node merge(const node &left, const node &right) {
        node ans;
        ans.l = left.l;
        ans.r = right.r;

        if (left.size() == 1) {
            for (path &p : min_dist[left.l][right.r].min) {
                if (p.length > 0) {
                    ans.combo.push_back(p);
                }
            }
            return ans;
        }

        if (right.size() == 1) {
            combo<path[4]>(ans, left.combo, min_dist[left.r][right.l].min);
        } else {
            combo(ans, left.combo, right.combo, left.r, right.l);
        }

        return ans;
    }

    void build(int v = 1, int l = 0, int r = n - 1) {
        if (l == r) {
            st[v] = node(nums[l], nums[l], 1);
        } else {
            int m = (l + r) / 2;
            build(2 * v, l, m);
            build(2 * v + 1, m + 1, r);
            st[v] = merge(st[2 * v], st[2 * v + 1]);
        }
    }

    void upd(int x, int y, int v = 1, int l = 0, int r = n - 1) {
        if (l == r) {
            nums[x] = y;
            st[v] = node(nums[l], nums[l], 1);
        } else {
            int m = (l + r) / 2;
            if (x <= m) {
                upd(x, y, 2 * v, l, m);
            } else {
                upd(x, y, 2 * v + 1, m + 1, r);
            }
            st[v] = merge(st[2 * v], st[2 * v + 1]);
        }
    }
} st;

int segtree::n = 1;

bool set_vals(int x, int y, ll cost, int first, int last) {
    auto &cur = min_dist[x][y];
    bool ans = false;

    if (!cur.set[0]) {
        cur.min[0] = path(first, last, cost);
        cur.set[0] = true;
        ans = true;
    }

    if (!cur.set[1] && !same(cur.min[0].start, first)) {
        cur.min[1] = path(first, last, cost);
        cur.set[1] = true;
        ans = true;
    }

    if (!cur.set[2] && !same(cur.min[0].end, last)) {
        cur.min[2] = path(first, last, cost);
        cur.set[2] = true;
        ans = true;
    }

    if (!cur.set[3] && !same(cur.min[0].start, first) && !same(cur.min[0].end, last)) {
        cur.min[3] = path(first, last, cost);
        cur.set[2] = true;
        ans = true;
    }

    return ans;
}

void dijk(int x) {
    // {dist, pos, first edge, last edge}
    priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;
    min_dist[x][x].set[0] = true;

    for (int e : adj[x]) {
        auto [nxt, cost] = edge[e];
        pq.push({cost, nxt, e, e});
    }

    while (!pq.empty()) {
        auto [cost, pos, first, last] = pq.top();
        pq.pop();

        bool res = set_vals(x, pos, cost, first, last);
        if (!res) continue;

        for (int e : adj[pos]) {
            if (!same(e, last)) {
                auto [nxt, cost2] = edge[e];
                pq.push({cost + cost2, nxt, first, e});
            }
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m >> t >> l;
    for (int i = 0; i < m; i++) {
        int a, b; ll c;
        cin >> a >> b >> c;
        a--; b--;
        adj[a].push_back(edge.size());
        edge.push_back({b, c});
        adj[b].push_back(edge.size());
        edge.push_back({a, c});
    }

    for (int i = 0; i < n; i++) {
        dijk(i);
    }

    for (int i = 0; i < l; i++) {
        cin >> nums[i];
        nums[i]--;
    }

    segtree::n = l;
    st.build();

    for (int i = 0; i < t; i++) {
        int p, q; cin >> p >> q;
        p--; q--;
        st.upd(p, q); 

        if (st.st[1].combo.empty()) {
            cout << "-1\n";
        } else {
            ll ans = INFLL;
            for (auto &p : st.st[1].combo) {
                ans = min(ans, p.length);
            }
            cout << ans << '\n';
        }
    }

    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38