Submission #1213259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213259		guagua0407	Sky Walking (IOI19_walk)	C++20	10 / 100	4105 ms	496960 KiB

walk

#include "walk.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    const ll inf=(ll)1e18;
}

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
    int n=(int)x.size();
    int m=(int)l.size();
    vector<vector<int>> ys(n);
    for(int i=0;i<n;i++){
        ys[i].push_back(0);
    }
    for(int i=0;i<m;i++){
        for(int j=l[i];j<=r[i];j++){
            if(y[i]<=h[j]){
                ys[j].push_back(y[i]);
            }
        }
    }
    vector<vector<int>> id(n);
    int cnt=0;
    for(int i=0;i<n;i++){
        sort(all(ys[i]));
        ys[i].resize(unique(all(ys[i]))-ys[i].begin());
        id[i].resize(ys[i].size());
        for(int j=0;j<(int)id[i].size();j++){
            id[i][j]=cnt++;
        }
    }
    vector<vector<pair<int,int>>> adj(cnt);
    auto add_edge=[&](int a,int b,int c){
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    };
    for(int i=0;i<n;i++){
        for(int j=0;j<(int)ys[i].size()-1;j++){
            add_edge(id[i][j],id[i][j+1],ys[i][j+1]-ys[i][j]);
        }
    }
    for(int i=0;i<m;i++){
        vector<pair<int,int>> tmp;
        for(int j=l[i];j<=r[i];j++){
            if(y[i]<=h[j]){
                int pos=lower_bound(all(ys[j]),y[i])-ys[j].begin();
                tmp.push_back({j,id[j][pos]});
            }
        }
        for(int j=0;j<(int)tmp.size()-1;j++){
            add_edge(tmp[j].s,tmp[j+1].s,x[tmp[j+1].f]-x[tmp[j].f]);
        }
    }
    vector<ll> d(cnt,inf);
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    d[id[s][0]]=0;
    pq.push({0,id[s][0]});
    while(!pq.empty()){
        auto v=pq.top();
        pq.pop();
        if(v.f!=d[v.s]) continue;
        for(auto u:adj[v.s]){
            if(d[v.s]+u.s<d[u.f]){
                d[u.f]=d[v.s]+u.s;
                pq.push({d[u.f],u.f});
            }
        }
    }
    int en=id[g][0];
	return (d[en]==inf?-1:d[en]);
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43