oj.uz

Submission #1092633

# Submission time Handle Problem Language Result Execution time Memory
1092633 2024-09-24T16:02:04 Z nguyentunglam Train (APIO24_train) C++17
5 / 100
 1000 ms 15932 KB 
// #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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct.
2 Correct 1 ms 348 KB Correct.
3 Correct 1 ms 604 KB Correct.
4 Correct 1 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 11532 KB Correct.
2 Correct 95 ms 15816 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 9 ms 3932 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 163 ms 11716 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Execution timed out 1094 ms 15932 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 11532 KB Correct.
2 Correct 95 ms 15816 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 9 ms 3932 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 163 ms 11716 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Execution timed out 1094 ms 15932 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct.
2 Correct 1 ms 348 KB Correct.
3 Correct 1 ms 604 KB Correct.
4 Correct 1 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 87 ms 11532 KB Correct.
9 Correct 95 ms 15816 KB Correct.
10 Correct 1 ms 348 KB Correct.
11 Correct 9 ms 3932 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 163 ms 11716 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Execution timed out 1094 ms 15932 KB Time limit exceeded
16 Halted 0 ms 0 KB -