Submission #1283189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283189		abc123	Train (APIO24_train)	C++20	5 / 100	1082 ms	10828 KiB

train

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int y, a, b;
    long long c;
};

struct State {
    long long t, cost;
    int v, mask;
    bool operator<(const State &o) const {
        return cost > o.cost;
    }
};

long long solve(int N, int M, int W, vector<int> T,
                vector<int> X, vector<int> Y,
                vector<int> A, vector<int> B, vector<int> C,
                vector<int> L, vector<int> R) {
    vector<vector<Edge>> g(N);
    for (int i = 0; i < M; i++) {
        g[X[i]].push_back({Y[i], A[i], B[i], (long long)C[i]});
    }
    const long long INF = 4e18;
    unordered_map<long long, long long> dist;  // encode (v<<10) | mask
    auto key = [&](int v, int m) { return ((long long)v << 10) | m; };
    priority_queue<State> pq;
    pq.push({0, 0, 0, 0});
    dist[key(0, 0)] = 0;

    while (!pq.empty()) {
        auto [t, c, v, mask] = pq.top();
        pq.pop();
        if (dist[key(v, mask)] < c) continue;
        if (v == N - 1 && mask == (1 << W) - 1) {
            return c;
        }

        // Take meals on current planet for cost if meal time is exactly inside waiting period
        for (int i = 0; i < W; i++) {
            if (!(mask & (1 << i)) && L[i] <= t && t <= R[i]) {
                int nmask = mask | (1 << i);
                long long nc = c + T[v];
                if (!dist.count(key(v, nmask)) || dist[key(v, nmask)] > nc) {
                    dist[key(v, nmask)] = nc;
                    pq.push({t, nc, v, nmask});
                }
            }
        }

        // Take train routes from current planet at or after current time
        for (auto &e : g[v]) {
            if (e.a >= t) {
                int nmask = mask;
                for (int i = 0; i < W; i++) {
                    // Meal must be fully inside train interval to be free
                    if (!(mask & (1 << i)) && L[i] >= e.a && R[i] <= e.b) {
                        nmask |= (1 << i);
                    }
                }
                long long nc = c + e.c;
                if (!dist.count(key(e.y, nmask)) || dist[key(e.y, nmask)] > nc) {
                    dist[key(e.y, nmask)] = nc;
                    pq.push({e.b, nc, e.y, nmask});
                }
            }
        }
    }
    return -1;
}

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60