Submission #220094

#	Time	Username	Problem	Language	Result	Execution time	Memory
220094		daniel920712	Sky Walking (IOI19_walk)	C++14	0 / 100	765 ms	37368 KiB

walk

#include "walk.h"
#include <map>
#include <utility>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
map < pair < long long , long long > , vector <  pair < long long , pair < long long , long long > > > > Next;
priority_queue < pair < long long , pair < long long , long long > > , vector < pair < long long , pair < long long , long long > > > , greater < pair < long long , pair < long long , long long > > > > all;
set < pair < long long , long long> > have;
vector < long long > xx[500005];
vector < long long > yy[500005];
bool F(long long a,long long b)
{
    return a<b;
}
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)
{
    long long N=(long long) x.size(),M=(long long) l.size(),t,i,j;
    for(i=0;i<N;i++)
    {
        xx[i].push_back(0);
        xx[i].push_back(h[i]);
    }
    for(i=0;i<M;i++)
    {
        yy[i].push_back(l[i]);
        yy[i].push_back(r[i]);
    }
    for(i=0;i<N;i++)
    {

        for(j=0;j<M;j++)
        {
            if(l[j]<=x[i]&&x[i]<=r[j]&&y[j]<=h[i])
            {
                xx[i].push_back(y[j]);
                yy[j].push_back(x[i]);
            }
        }
    }
    for(i=0;i<N;i++)
    {
        sort(xx[i].begin(),xx[i].end(),F);
        t=(long long) xx[i].size();
        for(j=1;j<t;j++)
        {
            Next[make_pair(x[i],xx[i][j-1])].push_back(make_pair(xx[i][j]-xx[i][j-1],make_pair(x[i],xx[i][j])));
            Next[make_pair(x[i],xx[i][j])].push_back(make_pair(xx[i][j]-xx[i][j-1],make_pair(x[i],xx[i][j-1])));
        }
    }
    for(i=0;i<M;i++)
    {
        sort(yy[i].begin(),yy[i].end(),F);
        t=(long long) yy[i].size();
        for(j=1;j<t;j++)
        {
            Next[make_pair(yy[i][j-1],y[i])].push_back(make_pair(yy[i][j]-yy[i][j-1],make_pair(yy[i][j],y[i])));
            Next[make_pair(yy[i][j],y[i])].push_back(make_pair(yy[i][j]-yy[i][j-1],make_pair(yy[i][j-1],y[i])));
        }
    }
    all.push(make_pair((long long)0,make_pair((long long)s,(long long)0)));
    while(!all.empty())
    {
        auto xx=all.top();
        all.pop();
        if(xx.second==make_pair((long long) g,(long long)0)) return xx.first;
        if(have.find(xx.second)!=have.end()) continue;
        for(auto i:Next[xx.second]) all.push(make_pair(xx.first+i.first,i.second));
    }
	return -1;
}

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