Submission #1213271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213271		guagua0407	Sky Walking (IOI19_walk)	C++20	10 / 100	4096 ms	476772 KiB

walk

#pragma GCC optimize("O3")
#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) {
    auto st=clock();
    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<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]=cnt;
        cnt+=(int)ys[i].size();
    }
    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;
    pq.push({0,id[s]});
    int en=id[g];
    while(!pq.empty() and clock()-st<3*CLOCKS_PER_SEC){
        auto v=pq.top();
        pq.pop();
        if(v.f!=d[v.s]) continue;
        if(v.s==en) return v.f;
        for(auto u:adj[v.s]){
            if(clock()-st>3*CLOCKS_PER_SEC) break;
            if(d[v.s]+u.s<d[u.f]){
                d[u.f]=d[v.s]+u.s;
                pq.push({d[u.f],u.f});
            }
        }
    }
	return -1;
}

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