oj.uz

Submission #768365

# Submission time Handle Problem Language Result Execution time Memory
768365 2023-06-28T02:16:54 Z hgmhc None (JOI14_ho_t4) C++17
25 / 100
 107 ms 12972 KB 
#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define all(x) begin(x),end(x)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
using namespace std;
using ll = long long;
using ii = pair<int,int>;
#define dbg(...) fprintf(stderr,__VA_ARGS__)

const ll INF = 1e18;
const int N = 1e5+3;
int n, m, x, h[N];
vector<ii> adj[N];
ll dist[N];

int main() {
    scanf("%d%d%d", &n, &m, &x);
    rep(i,1,n) scanf("%d", &h[i]);
    rep(i,1,m) {
        int u, v, t;
        scanf("%d%d%d", &u, &v, &t);
        if (h[u] >= t) adj[u].push_back({v,t});
        if (h[v] >= t) adj[v].push_back({u,t});
    }
    fill(dist,dist+N,INF);
    priority_queue<pair<ll,int>> pq;
    dist[1] = 0, pq.push({0,1});
    while (not empty(pq)) {
        auto [d,a] = pq.top(); pq.pop(), d=-d;
        if (dist[a] < d) continue;
        for (auto [b,w] : adj[a]) {
            if (dist[a] < x) {
                if (x-dist[a] >= w) {
                    dist[b] = max(dist[a]+w,0LL+x-h[b]);
                } else {
                    dist[b] = dist[a]+w-(x-dist[a]);
                }
                pq.push({-dist[b],b});
            }
            else if (dist[b] > dist[a]+2*w) {
                dist[b] = dist[a]+2*w;
                pq.push({-dist[b],b});
            }
        }
    }
    if (h[n]+dist[n] >= INF) puts("-1");
    else printf("%lld", h[n]+dist[n]);
}

Compilation message

2014_ho_t4.cpp: In function 'int main()':
2014_ho_t4.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d%d%d", &n, &m, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:20:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     rep(i,1,n) scanf("%d", &h[i]);
      |                ~~~~~^~~~~~~~~~~~~
2014_ho_t4.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d%d%d", &u, &v, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 3 ms 3412 KB Output is correct
3 Incorrect 3 ms 3540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 6768 KB Output is correct
2 Correct 90 ms 12896 KB Output is correct
3 Correct 64 ms 8344 KB Output is correct
4 Correct 107 ms 12972 KB Output is correct
5 Correct 83 ms 12484 KB Output is correct
6 Correct 5 ms 3412 KB Output is correct
7 Correct 61 ms 3800 KB Output is correct
8 Correct 102 ms 11228 KB Output is correct
9 Correct 68 ms 4984 KB Output is correct
10 Correct 45 ms 4044 KB Output is correct
11 Correct 12 ms 4436 KB Output is correct
12 Correct 60 ms 7812 KB Output is correct
13 Correct 30 ms 7756 KB Output is correct
14 Correct 88 ms 4432 KB Output is correct
15 Correct 4 ms 3540 KB Output is correct
16 Correct 84 ms 12368 KB Output is correct
17 Correct 12 ms 4168 KB Output is correct
18 Correct 12 ms 4216 KB Output is correct
19 Correct 27 ms 3584 KB Output is correct
20 Correct 14 ms 4400 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 3 ms 3412 KB Output is correct
3 Incorrect 3 ms 3540 KB Output isn't correct
4 Halted 0 ms 0 KB -