oj.uz

Submission #824485

# Submission time Handle Problem Language Result Execution time Memory
824485 2023-08-14T06:51:13 Z Magikarp4000 Sky Walking (IOI19_walk) C++17
10 / 100
 1786 ms 1048576 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 = 5e6+10;
int n,m;
vector<pair<int,ll>> v[MAXX];
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 68 ms 120016 KB Output is correct
2 Correct 65 ms 119960 KB Output is correct
3 Correct 60 ms 119972 KB Output is correct
4 Correct 59 ms 119960 KB Output is correct
5 Correct 61 ms 120112 KB Output is correct
6 Correct 60 ms 120092 KB Output is correct
7 Correct 59 ms 120052 KB Output is correct
8 Correct 61 ms 120064 KB Output is correct
9 Correct 63 ms 120012 KB Output is correct
10 Correct 61 ms 120120 KB Output is correct
11 Correct 69 ms 120100 KB Output is correct
12 Correct 64 ms 120032 KB Output is correct
13 Correct 61 ms 120036 KB Output is correct
14 Correct 61 ms 119988 KB Output is correct
15 Correct 61 ms 120028 KB Output is correct
16 Correct 61 ms 120036 KB Output is correct
17 Correct 66 ms 120180 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 119944 KB Output is correct
2 Correct 62 ms 120036 KB Output is correct
3 Correct 773 ms 267008 KB Output is correct
4 Correct 816 ms 267664 KB Output is correct
5 Runtime error 1786 ms 1048576 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 130848 KB Output is correct
2 Runtime error 1729 ms 1048576 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 117 ms 130848 KB Output is correct
2 Runtime error 1729 ms 1048576 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 68 ms 120016 KB Output is correct
2 Correct 65 ms 119960 KB Output is correct
3 Correct 60 ms 119972 KB Output is correct
4 Correct 59 ms 119960 KB Output is correct
5 Correct 61 ms 120112 KB Output is correct
6 Correct 60 ms 120092 KB Output is correct
7 Correct 59 ms 120052 KB Output is correct
8 Correct 61 ms 120064 KB Output is correct
9 Correct 63 ms 120012 KB Output is correct
10 Correct 61 ms 120120 KB Output is correct
11 Correct 69 ms 120100 KB Output is correct
12 Correct 64 ms 120032 KB Output is correct
13 Correct 61 ms 120036 KB Output is correct
14 Correct 61 ms 119988 KB Output is correct
15 Correct 61 ms 120028 KB Output is correct
16 Correct 61 ms 120036 KB Output is correct
17 Correct 66 ms 120180 KB Output is correct
18 Correct 62 ms 119944 KB Output is correct
19 Correct 62 ms 120036 KB Output is correct
20 Correct 773 ms 267008 KB Output is correct
21 Correct 816 ms 267664 KB Output is correct
22 Runtime error 1786 ms 1048576 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -