제출 #286279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286279		MKopchev	Sky Walking (IOI19_walk)	C++14	24 / 100	4125 ms	525268 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,mem_h;

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);
}

int stop=0;

void dij(pair<int,int> start)
{
    pq.push({0,start});

    while(pq.size()&&mem.count({stop,0})==0)
    {
        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});
    }
}

vector< pair<int,int> > tree[4*nmax];

void build(int node,int l,int r)
{
    if(l==r)
    {
        tree[node].push_back({mem_h[l],l});
        return;
    }

    int av=(l+r)/2;

    build(node*2,l,av);
    build(node*2+1,av+1,r);

    tree[node]=tree[node*2];

    for(auto k:tree[node*2+1])
        tree[node].push_back(k);

    sort(tree[node].begin(),tree[node].end());
}

vector<int> given;

void query(int node,int l,int r,int lq,int rq,int low)
{
    if(l==lq&&r==rq)
    {
        int pointer=tree[node].size()-1;

        while(pointer>=0&&tree[node][pointer].first>=low)
        {
            given.push_back(tree[node][pointer].second);
            pointer--;
        }
        return;
    }
    int av=(l+r)/2;

    if(lq<=av)query(node*2,l,av,lq,min(av,rq),low);
    if(av<rq)query(node*2+1,av+1,r,max(av+1,lq),rq,low);
}
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)
{
    stop=g;

    mem_x=x;
    mem_h=h;

    build(1,0,x.size()-1);

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

        given={};

        query(1,0,x.size()-1,l[t],r[t],y[t]);

        sort(given.begin(),given.end());

        for(auto j:given)
            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});

    if(mem.count({g,0}))return mem[{g,0}];
    return -1;
}

컴파일 시 표준 에러 (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:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int t=0;t<l.size();t++)
      |                 ~^~~~~~~~~
walk.cpp:126:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~

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