Submission #824480

#	Time	Username	Problem	Language	Result	Execution time	Memory
824480		Magikarp4000	Sky Walking (IOI19_walk)	C++17	10 / 100	63 ms	38596 KiB

walk

#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 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43