Submission #1129059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129059		crafticat	Wild Boar (JOI18_wild_boar)	C++17	0 / 100	0 ms	320 KiB

wild_boar

#include <bits/stdc++.h>

#include <bits/stdc++.h>

using namespace std;
template<typename T>
using V = vector<T>;
#define s second
#define F0R(i,n) for(int i = 0; i < n;i++)
#define FOR(i,j,n) for(int i = j; i < n;i++)
using ll = long long;
using vi = V<int>;
using pi = pair<int,int>;
#define f first
#define s second

map<pi, int> toId;
map<int,pi> fromId;

int nextId = 0;
constexpr int INF = 1e9;

int getId(pi edge) {
    if (toId.count(edge)) return toId[edge];
    fromId[nextId] = edge;

    return toId[edge] = nextId++;
}

V<V<pi>> constructG(V<V<pi>> &org, int M) {
    V<V<pi>> ans(M * 4 + 2);
    F0R(i, org.size()) {
        for (auto [j, c1] : org[i]) {
            int fromId = getId({i,j});
            for (auto [k, c2] : org[j]) {
                if (k == i) continue;
                int targetId = getId({j, k});
                ans[fromId].emplace_back(targetId, c2);
            }
        }
    }

    return ans;
}

V<V<pi>> g;

V<V<int>> computeDp() {
    int n = g.size();
    V<V<int>> ans(n, vi(n, INF));
    F0R(i, n) {
        ans[i][i] = 0;
        for (auto [y,c] : g[i]) {
            ans[i][y] = min(ans[i][y],c);
        }
    }

    F0R(i, n) {
        F0R(j, n) {
            F0R(k, n) {
                ans[j][k] = min(ans[j][k], ans[j][i] + ans[i][k]);
            }
        }
    }
    return ans;
}

void update(pi &x, int id, int cost, const V<int> &dp) {
    if (x.f == -1 or dp[x.f] > cost) {
        x.s = x.f;
        x.f = id;
        return;
    }
    if (x.s == -1 or dp[x.s] > cost)
        x.s = id;
}

//dp[18][8]
V<V<pi>> getBests(V<V<int>> dp, int n) {
    V<V<pi>> ans(dp.size(), V<pi>(dp.size(), {-1, -1}));

    F0R(i, dp.size()) {
        F0R(j, dp.size()) {
            auto [a,b] = fromId[j];
            update(ans[i][b], j, dp[i][j], dp[i]);
        }
    }
    return ans;
}

V<pi> removeDup(V<pi> arr) {
    set<int> exists;
    V<pi> ans;
    for (auto [x,y] : arr) {
        if (exists.count(y)) continue;
        exists.insert(y);
        ans.emplace_back(x,y);
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n, m, t, l; cin >> n >> m >> t >> l;
    V<V<pi>> gOrg(n * 2 + 2);

    //11
    F0R(i, m) {
        int x, y, c; cin >> x >> y >> c;
        gOrg[x].push_back({y,c});
        gOrg[y].push_back({x,c});
    }
    F0R(i, n) {
        gOrg[m + i + 1].push_back({i + 1,0});
        gOrg[i + 1].push_back({m + i  +1,0});
    }

    g = constructG(gOrg, m);
    V<V<int>> dp = computeDp();
    V<V<pi>> targets = getBests(dp, n);

    vi order(l);
    F0R(i, l)
        cin >> order[i];

    F0R(i, t) {
        int x, y; cin >> x >> y; x--;
        order[x] = y;

        V<pi> path;
        int id = getId({y + m,order[0]});
        path.emplace_back(0, id);

        // 2 -> 5 (id = 1)
        // 4 -> 5 (id = 8)

        FOR(test, 1, order.size()) {
            int target = order[test];
            V<pi> newPath;
            for (auto [cost, v] : path) {
                pi v2 = targets[v][target];
                newPath.emplace_back(dp[v][v2.f] + cost,v2.f);
                newPath.emplace_back(dp[v][v2.s] + cost,v2.s);
            }

            std::sort(newPath.begin(), newPath.end());
            newPath = removeDup(newPath);
            path = {newPath[0]};
            if (newPath.size() > 1) path.push_back(newPath[1]);
        }

        int ans = INF;
        for (auto [cost, v] : path)
            ans = min(cost, ans);

        if (ans == INF) {
            cout << "-1\n";
            continue;
        }
        cout << ans << "\n";
    }


    return 0;
}

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