Submission #286256

#	Time	Username	Problem	Language	Result	Execution time	Memory
286256		MKopchev	Sky Walking (IOI19_walk)	C++14	0 / 100	4111 ms	526976 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+42;

map< pair<int,int>, vector< pair<int,int> > >edges;

map< pair<int,int>,long long> mem;

set<int> seen[nmax];

priority_queue< pair<long long,pair<int,int> > > pq;

vector<int> mem_x;

int dist(pair<int,int> a,pair<int,int> b)
{
    return abs(mem_x[a.first]-mem_x[b.first])+abs(a.second-b.second);
}
void dij(pair<int,int> start)
{
    pq.push({0,start});

    while(pq.size())
    {
        pair<long long,pair<int,int> > tp=pq.top();
        pq.pop();

        if(mem.count(tp.second))continue;

        tp.first=-tp.first;

        mem[tp.second]=tp.first;

        //cout<<tp.first<<" "<<tp.second.first<<" "<<tp.second.second<<endl;

        for(auto k:edges[tp.second])
            pq.push({-(dist(k,tp.second)+tp.first),k});
    }
}
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)
{
    mem_x=x;

    for(int t=0;t<l.size();t++)
    {
        int prv=-1;

        for(int j=l[t];j<=r[t];j++)
            if(h[j]>=y[t])
            {
                seen[j].insert(y[t]);

                if(prv!=-1)
                {
                    edges[{j,y[t]}].push_back({prv,y[t]});
                    edges[{prv,y[t]}].push_back({j,y[t]});
                }

                prv=j;
            }
    }

    seen[s].insert(0);
    seen[g].insert(0);

    for(int i=0;i<x.size();i++)
    {
        int prv=-1;

        for(auto k:seen[i])
        {
            if(prv!=-1)
            {
                edges[{i,prv}].push_back({i,k});
                edges[{i,k}].push_back({i,prv});
            }

            prv=k;
        }
    }

    dij({s,0});

    return mem[{g,0}];
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int t=0;t<l.size();t++)
      |                 ~^~~~~~~~~
walk.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~

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