Submission #1291410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291410		MMihalev	Sky Walking (IOI19_walk)	C++20	10 / 100	4125 ms	727572 KiB

walk

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<cstring>
#include<set>
#include<queue>
#include "walk.h"
using namespace std;
const int MAX_N=3e6+5;
int N;
int szx;
int szpoints;
map<pair<int,int>,int>pospoint;
map<int,int>posx;
set<int>pointsx[MAX_N];
int right[MAX_N];
int up[MAX_N];
void add_point(int x,int y)
{
    if(pospoint.find({x,y})==pospoint.end())
    {
        pospoint[{x,y}]=szpoints++;
    }
    pointsx[posx[x]].insert(y);
}
vector<pair<int,long long>>g[MAX_N];
long long dist[MAX_N];
void add_edge(int u,int v,int cost)
{
    g[u].push_back({v,cost});
    g[v].push_back({u,cost});
}
long long dijkstra(int s,int t)
{
    priority_queue<pair<long long,int>>q;
    q.push({0,s});
    memset(dist,-1,sizeof(dist));
    dist[s]=0;
    while(q.size())
    {
        long long d=-q.top().first;
        int u=q.top().second;
        q.pop();
        if(d>dist[u])continue;

        for(auto [v,edge]:g[u])
        {
            if(dist[u]+edge<dist[v] or dist[v]==-1)
            {
                dist[v]=dist[u]+edge;
                q.push({-dist[v],v});
            }
        }
    }

    return dist[t];
}
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)
{
    N=x.size();

    if(N==1)return 0;

    for(int i=0;i<x.size();i++)
    {
        if(posx.find(x[i])==posx.end())
        {
            posx[x[i]]=szx++;
        }
    }

    for(int i=0;i<x.size();i++)
    {
        add_point(x[i],0);
        add_point(x[i],h[i]);

        add_edge(szpoints-1,szpoints-2,h[i]);
    }

    vector<pair<int,int>>order;

    for(int i=0;i<y.size();i++)
    {
        order.push_back({y[i],i});
    }
    sort(order.begin(),order.end());

    for(int id=0;id<l.size();id++)
    {
        int i=order[id].second;

        int prevx=-1,prevy;
        for(int j=l[i];j<=r[i];j++)
        {
            if(h[j]>=y[i])
            {
                add_point(x[j],y[i]);
            }
            else continue;

            if(prevx!=-1)
            {
                add_edge(pospoint[{prevx,prevy}],pospoint[{x[j],y[i]}],x[j]-prevx);
            }

            auto it=pointsx[posx[x[j]]].lower_bound(y[i]);
            it--;

            int yy=((*it));
            add_edge(pospoint[{x[j],yy}],pospoint[{x[j],y[i]}],y[i]-yy);

            prevx=x[j];
            prevy=y[i];
        }
    }

    return dijkstra(pospoint[{x[s],0}],pospoint[{x[g],0}]);
}

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