oj.uz

Submission #418125

# Submission time Handle Problem Language Result Execution time Memory
418125 2021-06-05T06:34:10 Z usachevd0 Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 838036 KB 
#include <bits/stdc++.h>
#ifndef LOCAL
    #include "walk.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& x : v)
        stream << x << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}

const ll INF64 = 1e18;
const int maxN = 100005;
int n, m;

const int maxV = 4e6 + 6;
int V;
vector<pii> G[maxV];
ll dist[maxV];
priority_queue<pli> pq;

map<int, int> ptIdx[maxN];
int getIdx(int x, int y) {
    if (ptIdx[x].count(y))
        return ptIdx[x][y];
    // debug(x, y, V);
    return ptIdx[x][y] = V++;
}

void addEdge(int u, int v, int w) {
    // debug(u, v, w);
    G[u].emplace_back(v, w);
    G[v].emplace_back(u, w);
}

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int SI, int TI) {
    n = X.size(), m = L.size();
    
    int S, T;
    for (int i = 0; i < n; ++i) {
        int v = getIdx(i, 0);
        if (i == SI)
            S = v;
        if (i == TI)
            T = v;
    }
    // debug(S, T);
    for (int j = 0; j < m; ++j) {
        int l = L[j], r = R[j], y = Y[j];
        int last_i = l, last_v = getIdx(l, y);
        for (int i = l + 1; i <= r; ++i) {
            if (H[i] >= y) {
                int v = getIdx(i, y);
                addEdge(last_v, v, X[i] - X[last_i]);
                last_v = v;
                last_i = i;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        int last_y = -1, last_v = -1;
        for (auto& [y, v] : ptIdx[i]) {
            if (last_y != -1) {
                addEdge(last_v, v, y - last_y);
            }
            last_y = y;
            last_v = v;
        }
    }
    
    fill(dist, dist + V, INF64);
    dist[S] = 0;
    pq.push({0, S});
    while (!pq.empty()) {
        ll _d = -pq.top().fi;
        int v = pq.top().se;
        pq.pop();
        if (_d != dist[v]) continue;
        // debug(v, dist[v]);
        if (v == T) return dist[v];
        for (auto& [u, w] : G[v])
            if (chkmin(dist[u], dist[v] + w))
                pq.push({-dist[u], u});
    }
    return -1;
}


#ifdef LOCAL

int32_t main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    
        int n, m;
    assert(2 == scanf("%d%d", &n, &m));
    vector<int> x(n), h(n);
    for (int i = 0; i < n; i++)
        assert(2 == scanf("%d%d", &x[i], &h[i]));
    vector<int> l(m), r(m), y(m);
    for (int i = 0; i < m; i++)
        assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
    int s, g;
    assert(2 == scanf("%d%d", &s, &g));
    fclose(stdin);

    long long result = min_distance(x, h, l, r, y, s, g);

    printf("%lld\n", result);
    fclose(stdout);
    
    return 0;
}

#endif

Compilation message

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:123:9: warning: 'T' may be used uninitialized in this function [-Wmaybe-uninitialized]
  123 |         if (v == T) return dist[v];
      |         ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 98880 KB Output is correct
2 Correct 53 ms 98872 KB Output is correct
3 Correct 52 ms 98832 KB Output is correct
4 Correct 54 ms 98872 KB Output is correct
5 Correct 54 ms 98948 KB Output is correct
6 Correct 53 ms 98884 KB Output is correct
7 Correct 53 ms 98980 KB Output is correct
8 Correct 52 ms 98880 KB Output is correct
9 Correct 54 ms 98828 KB Output is correct
10 Correct 56 ms 98928 KB Output is correct
11 Correct 53 ms 98840 KB Output is correct
12 Correct 53 ms 98932 KB Output is correct
13 Correct 53 ms 98900 KB Output is correct
14 Correct 54 ms 98836 KB Output is correct
15 Correct 54 ms 98888 KB Output is correct
16 Correct 53 ms 98820 KB Output is correct
17 Correct 53 ms 99008 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 98884 KB Output is correct
2 Correct 53 ms 98884 KB Output is correct
3 Correct 738 ms 191940 KB Output is correct
4 Correct 762 ms 202824 KB Output is correct
5 Correct 492 ms 188852 KB Output is correct
6 Correct 727 ms 178200 KB Output is correct
7 Correct 495 ms 188868 KB Output is correct
8 Correct 977 ms 219644 KB Output is correct
9 Correct 565 ms 187588 KB Output is correct
10 Correct 1037 ms 243008 KB Output is correct
11 Correct 397 ms 150084 KB Output is correct
12 Correct 279 ms 134204 KB Output is correct
13 Correct 896 ms 225224 KB Output is correct
14 Correct 1723 ms 132736 KB Output is correct
15 Correct 1025 ms 133512 KB Output is correct
16 Correct 347 ms 134648 KB Output is correct
17 Correct 317 ms 132724 KB Output is correct
18 Execution timed out 4070 ms 120804 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 108724 KB Output is correct
2 Runtime error 2362 ms 838036 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 108724 KB Output is correct
2 Runtime error 2362 ms 838036 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 98880 KB Output is correct
2 Correct 53 ms 98872 KB Output is correct
3 Correct 52 ms 98832 KB Output is correct
4 Correct 54 ms 98872 KB Output is correct
5 Correct 54 ms 98948 KB Output is correct
6 Correct 53 ms 98884 KB Output is correct
7 Correct 53 ms 98980 KB Output is correct
8 Correct 52 ms 98880 KB Output is correct
9 Correct 54 ms 98828 KB Output is correct
10 Correct 56 ms 98928 KB Output is correct
11 Correct 53 ms 98840 KB Output is correct
12 Correct 53 ms 98932 KB Output is correct
13 Correct 53 ms 98900 KB Output is correct
14 Correct 54 ms 98836 KB Output is correct
15 Correct 54 ms 98888 KB Output is correct
16 Correct 53 ms 98820 KB Output is correct
17 Correct 53 ms 99008 KB Output is correct
18 Correct 54 ms 98884 KB Output is correct
19 Correct 53 ms 98884 KB Output is correct
20 Correct 738 ms 191940 KB Output is correct
21 Correct 762 ms 202824 KB Output is correct
22 Correct 492 ms 188852 KB Output is correct
23 Correct 727 ms 178200 KB Output is correct
24 Correct 495 ms 188868 KB Output is correct
25 Correct 977 ms 219644 KB Output is correct
26 Correct 565 ms 187588 KB Output is correct
27 Correct 1037 ms 243008 KB Output is correct
28 Correct 397 ms 150084 KB Output is correct
29 Correct 279 ms 134204 KB Output is correct
30 Correct 896 ms 225224 KB Output is correct
31 Correct 1723 ms 132736 KB Output is correct
32 Correct 1025 ms 133512 KB Output is correct
33 Correct 347 ms 134648 KB Output is correct
34 Correct 317 ms 132724 KB Output is correct
35 Execution timed out 4070 ms 120804 KB Time limit exceeded
36 Halted 0 ms 0 KB -