Submission #380312

#	Time	Username	Problem	Language	Result	Execution time	Memory
380312		fishy15	Wild Boar (JOI18_wild_boar)	C++17	12 / 100	199 ms	195436 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 2010
#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 {
    vector<path> min;
};

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;
}

bool set_vals(vector<path> &cur, ll cost, int first, int last) {
    if (cur.size() >= 5) return false;

    int x_cnt = 0;
    int y_cnt = 0;
    for (auto &p : cur) {
        if (p.start == first) x_cnt++;
        if (p.end == last) y_cnt++;
        if (p.start == first && p.end == last) return false;
    }

    if (x_cnt < 2 && y_cnt < 2) {
        cur.emplace_back(first, last, cost);
        return true;
    }

    return false;
}

// 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 sz; }
    };

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

    void combo(node &ans, const vector<path> &left, const vector<path> &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);
                }
            }
        }

        vector<path> v;
        for (auto p : m) {
            v.emplace_back(p.first.first, p.first.second, p.second);
        }

        sort(v.begin(), v.end(), [](const path &p1, const path &p2) {
            return p1.length < p2.length;
        });

        for (auto p : v) {
            set_vals(ans.combo, p.length, p.start, p.end);
        }
    }

    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);
                    }
                }
            }
        }
        vector<path> v;

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

        sort(v.begin(), v.end(), [](const path &p1, const path &p2) {
            return p1.length < p2.length;
        });

        for (auto p : v) {
            set_vals(ans.combo, p.length, p.start, p.end);
        }
    }

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

        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(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;

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].min.emplace_back(x, x, 0);

    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(min_dist[x][pos].min, 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: 12 / 12
• Subtask 2: 0 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38