Submission #1092633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092633		nguyentunglam	Train (APIO24_train)	C++17	5 / 100	1094 ms	15932 KiB

train

// #include "train.h"
#include<bits/stdc++.h>
using namespace std;
 
#include <cassert>
#include <cstdio>
 
#include <vector>
 
 
long long solve(int n, int m, int w, std::vector<int> t, std::vector<int> x, std::vector<int> y,
                std::vector<int> a, std::vector<int> b, std::vector<int> c, std::vector<int> l,
                std::vector<int> r) 
{
    vector<int> rrh;

    for (int i = 0; i < m; i++) {
        rrh.push_back(a[i]);
        rrh.push_back(b[i]);
    }
    for (int i = 0; i < w; i++) {
        rrh.push_back(l[i]);
        rrh.push_back(r[i]);
    }

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

    auto find_idx = [&] (int x) {
        return upper_bound(rrh.begin(), rrh.end(), x) - rrh.begin();
    };

    for (int i = 0; i < m; i++) {
        a[i] = find_idx(a[i]);
        b[i] = find_idx(b[i]);
    }

    for (int i = 0; i < w; i++) {
        l[i] = find_idx(l[i]);
        r[i] = find_idx(r[i]);
    }

    vector<vector<int> > adj(n);
 
    for (int i = 0; i < m; i++) {
        adj[x[i]].push_back(i);
    }
 
    #define ii pair<long long, int> 
    priority_queue<ii, vector<ii>, greater<ii> > q;
 
    vector<long long> f(m);
 
    for (int i = 0; i < m; i++) f[i] = 1e18;
 
    for (int &i : adj[0]) {
        long long extra = 0;
        for (int j = 0; j < w; j++) {
            if (r[j] < a[i]) extra += t[0];
        }
        q.push({f[i] = extra + c[i], i});
    }
 
    while (!q.empty()) {
        auto [cost, pre] = q.top(); q.pop();
        for (int &nxt : adj[y[pre]]) if (a[nxt] >= b[pre]) {
            long long extra = 0;
            for (int j = 0; j < w; j++) {
                if (b[pre] < l[j] && r[j] < a[nxt]) extra += t[y[pre]];
            }
            if (f[nxt] > f[pre] + extra + c[nxt]) {
                q.push({f[nxt] = f[pre] + extra + c[nxt], nxt});
            }
        }
    }
 
    long long ans = 1e18;
 
    for (int i = 0; i < m; i++) if (y[i] == n - 1) {
        long long extra = 0;
        for (int j = 0; j < w; j++) if (l[j] > b[i]) extra += t[n - 1];
        ans = min(ans, extra + f[i]);
    }
 
    if (ans == 1e18) return -1;
    return ans;
 
}
 
 
#ifdef ngu
signed main() {
  int N, M, W;
  assert(3 == scanf("%d %d %d", &N, &M, &W));
  std::vector<int> t(N);
  std::vector<int> x(M);
  std::vector<int> y(M);
  std::vector<int> a(M);
  std::vector<int> b(M);
  std::vector<int> c(M);
  std::vector<int> l(W);
  std::vector<int> r(W);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &t[i]));
  for (int i = 0; i < M; i++)
    assert(5 == scanf("%d %d %d %d %d", &x[i], &y[i], &a[i], &b[i], &c[i]));
  for (int i = 0; i < W; i++)
    assert(2 == scanf("%d %d", &l[i], &r[i]));
  printf("%lld", solve(N, M, W, t, x, y, a, b, c, l, r));
}
#endif 

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