oj.uz

Submission #824480

# Submission time Handle Problem Language Result Execution time Memory
824480 2023-08-14T06:47:35 Z Magikarp4000 Sky Walking (IOI19_walk) C++17
10 / 100
 63 ms 38596 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 1e5+5, MAXX = 51;
int n,m;
vector<pair<int,ll>> v[MAXN];
UM<int,UM<int,int>> mp;
vector<int> pos[MAXN];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = x.size(), m = l.size();
    int cur = 0;
    FOR(i,0,m) {
        FOR(j,l[i],r[i]) {
            if (!mp[y[i]].count(x[j])) mp[y[i]][x[j]] = cur++;
            if (!mp[y[i]].count(x[j+1])) mp[y[i]][x[j+1]] = cur++;
            int a = mp[y[i]][x[j]], b = mp[y[i]][x[j+1]];
            // cout << "y x mp: " << y[i] << " " << x[j] << " " << mp[y[i]][x[j]] << ln;
            v[a].PB({b,1LL*(x[j+1]-x[j])});
            v[b].PB({a,1LL*(x[j+1]-x[j])});
            pos[j].PB(y[i]);
        }
        // cout << "y x mp: " << y[i] << " " << x[r[i]] << " " << mp[y[i]][x[r[i]]] << ln;
        pos[r[i]].PB(y[i]);
    }
    FOR(i,0,n) sort(ALL(pos[i]));
    FOR(i,0,n) {
        int pn = pos[i].size();
        FOR(j,0,pn-1) {
            if (pos[i][j] == pos[i][j+1]) continue;
            if (pos[i][j+1] > h[i]) continue;
            int a = mp[pos[i][j]][x[i]], b = mp[pos[i][j+1]][x[i]];
            v[a].PB({b,pos[i][j+1]-pos[i][j]});
            v[b].PB({a,pos[i][j+1]-pos[i][j]});
        }
    }
    int st = -1, en = -1;
    if (!pos[s].empty() && pos[s][0] <= h[s]) {
        st = cur;
        int a = mp[pos[s][0]][x[s]], b = cur++;
        v[a].PB({b,pos[s][0]});
        v[b].PB({a,pos[s][0]});
    }
    if (!pos[g].empty() && pos[g][0] <= h[g]) {
        en = cur;
        int a = mp[pos[g][0]][x[g]], b = cur++;
        v[a].PB({b,pos[g][0]});
        v[b].PB({a,pos[g][0]});
    }
    if (st == -1 || en == -1) return -1;
    // FOR(i,0,cur+1) {
    //     cout << i << ": ";
    //     FORX(u,v[i]) cout << u.F << " ";
    //     cout << ln;
    // }
    PQ<pair<ll,int>> pq;
    vector<ll> d(cur+1,LLINF);
    pq.push({0LL,st});
    d[st] = 0LL;
    while (!pq.empty()) {
        int t = pq.top().S;
        pq.pop();
        FORX(u,v[t]) {
            if (d[t]+u.S < d[u.F]) {
                d[u.F] = d[t]+u.S;
                pq.push({-d[u.F],u.F});
            }
        }
    }
    return (d[en] == LLINF ? -1LL : d[en]);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5000 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 3 ms 5004 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 2 ms 5016 KB Output is correct
15 Correct 3 ms 4996 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 4 ms 5076 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 5004 KB Output is correct
3 Runtime error 63 ms 38596 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 16468 KB Output is correct
2 Runtime error 59 ms 35984 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 52 ms 16468 KB Output is correct
2 Runtime error 59 ms 35984 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 3 ms 4948 KB Output is correct
2 Correct 3 ms 5000 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 3 ms 5004 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 2 ms 5016 KB Output is correct
15 Correct 3 ms 4996 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 4 ms 5076 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 2 ms 5004 KB Output is correct
20 Runtime error 63 ms 38596 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -