제출 #220095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
220095		daniel920712	Sky Walking (IOI19_walk)	C++14	10 / 100	4135 ms	937608 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(x[l[i]]);
        yy[i].push_back(x[r[i]]);
    }
    for(i=0;i<M;i++)
    {
        for(j=l[i];j<=r[i];j++)
        {
            if(y[i]<=h[j])
            {
                xx[j].push_back(y[i]);
                yy[i].push_back(x[j]);
            }
        }
    }
    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++)
        {
            //printf("aa %lld %lld %lld\n",x[i],xx[i][j-1],xx[i][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++)
        {
            //printf("bb %lld %lld %lld\n",y[i],yy[i][j-1],yy[i][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)x[s],(long long)0)));
    while(!all.empty())
    {
        auto xx=all.top();
        all.pop();
        if(xx.second==make_pair((long long) x[g],(long long)0)) return xx.first;
        if(have.find(xx.second)!=have.end()) continue;
        have.insert(xx.second);
        //printf("%lld %lld %lld\n",xx.second.first,xx.second.second,xx.first);
        for(auto i:Next[xx.second]) all.push(make_pair(xx.first+i.first,i.second));
    }
	return -1;
}

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