Submission #715939

#	Time	Username	Problem	Language	Result	Execution time	Memory
715939		walterw	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	9772 ms	493048 KiB

wild_boar

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

vector<array<ll, 3>> adj[2005];
pair<ll, ll> info[2005][2];

priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;
vector<array<ll, 3>> v[2005];

void add(int node, ll val, int edgeid) {
    if (info[node][0] == pair<ll, ll> {val, edgeid} || info[node][1] == pair<ll, ll> {val, edgeid}) {
        return;
    }

    if (val < info[node][0].first) {
        swap(info[node][0], info[node][1]);
        info[node][0] = {val, edgeid};

        pq.push({info[node][1].first, info[node][1].second, node, 1});
        pq.push({info[node][0].first, info[node][0].second, node, 0});
    } else if (val < info[node][1].first && edgeid != info[node][0].second) {
        info[node][1] = {val, edgeid};
        pq.push({info[node][1].first, info[node][1].second, node, 1});
    }
}

struct dataa {
    vector<array<ll, 3>> res;

    dataa(){}
    dataa (vector<array<ll, 3>> temp) {
        map<int, int> a, b;
        set<pair<int, int>> s;

        sort(temp.begin(), temp.end());

        for (auto [w, id1, id2] : temp) {
            if (a[id1] == 2 || b[id2] == 2 || s.count({id1, id2}) > 0) continue;

            a[id1]++; b[id2]++;
            s.insert({id1, id2});
            res.push_back({w, id1, id2});
            if (res.size() == 5) break;
        }
    }
};

dataa route[2005][2005];

int arr[100005];

dataa tree[4 * 100005];

dataa comb(dataa lhs, dataa rhs) {
    vector<array<ll, 3>> temp;

    for (auto [w, id, i2] : lhs.res) {
        for (auto [w2, idd, idd2] : rhs.res) {
            if (i2 == idd) continue;
            temp.push_back({w + w2, id, idd2});
        }
    }

    return dataa(temp);
}

void build(int x, int l, int r) {
    if (l == r) {
        tree[x] = route[arr[l]][arr[l + 1]];
        return;
    }

    int mid = (l + r) / 2;

    build(2 * x, l, mid);
    build(2 * x + 1, mid + 1, r);

    tree[x] = comb(tree[2 * x], tree[2 * x + 1]);
}

void update(int x, int l, int r, int upnode) {
    if (l == r) {
        tree[x] = route[arr[l]][arr[l + 1]];
        return;
    }

    int mid = (l + r) / 2;

    if (upnode <= mid) update(2 * x, l, mid, upnode);
    else update(2 * x + 1, mid + 1, r, upnode);

    tree[x] = comb(tree[2 * x], tree[2 * x + 1]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    ll n, m, t, l; cin >> n >> m >> t >> l;

    for (int i = 1; i <= m; i++) {
        ll a, b, c; cin >> a >> b >> c;
        adj[a].push_back({b, c, i});
        adj[b].push_back({a, c, i});
    }

    for (int x = 1; x <= n; x++) {
        // start from i
        for (int i = 1; i <= n; i++) v[i].clear();

        for (auto [temp, c, id] : adj[x]) {
            fill(&info[0][0], &info[0][0] + sizeof(info) / sizeof(info[0][0]), pair<ll, ll> ({1e17, -1}));

            add(temp, c, id);

            while (!pq.empty()) {
                auto cur = pq.top(); pq.pop();

                if (info[cur[2]][cur[3]] != pair<ll, ll> {cur[0], cur[1]})continue;

                for (auto [nxt, c2, id2] : adj[cur[2]]) {
                    if (cur[1] == id2) continue;
                    add(nxt, cur[0] + c2, id2);
                }
            }

            for (int i = 1; i <= n; i++) {
                if (info[i][0].first < 1e17) {
                    v[i].push_back({info[i][0].first, id, info[i][0].second});
                }

                if (info[i][1].first < 1e17) {
                    v[i].push_back({info[i][1].first, id, info[i][1].second});
                }
            }
        }

        for (int y = 1; y <= n; y++) {

            route[x][y] = dataa(v[y]);
        }
    }

    for (int i = 1; i <= l; i++) {
        cin >> arr[i];
    }

    build(1, 1, l-1);
//        cout << tree[1].res[0][0] << "\n";

    while (t--) {
        int a, b; cin >> a >> b;
        arr[a] = b;

        if (a != 1) {
            update(1, 1, l-1, a - 1);
        }

        if (a != (l)) {
            update(1, 1, l-1, a);
        }

        if (tree[1].res.empty()) cout << -1 << "\n";
        else cout << tree[1].res[0][0] << "\n";
    }
}

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