제출 #409665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409665		MKopchev	Sky Walking (IOI19_walk)	C++14	10 / 100	4062 ms	701644 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>

using namespace std;

const int nmax=1e5+42;

set<int> there[nmax];
map<int,int> id[nmax];
set<int> noted[nmax];

vector<long long> dist;

vector< vector< pair<int,int> > > adj;

vector<int> inp;

void add_edge(int x1,int y1,int x2,int y2)
{
    int p=id[x1][y1];
    int q=id[x2][y2];

    int d=abs(inp[x1]-inp[x2])+abs(y1-y2);

    //cout<<"x1= "<<x1<<" y1= "<<y1<<" x2= "<<x2<<" y2= "<<y2<<" d= "<<d<<" p= "<<p<<" q= "<<q<<endl;

    while(adj.size()<=p)adj.push_back({});
    while(adj.size()<=q)adj.push_back({});

    adj[p].push_back({q,d});
    adj[q].push_back({p,d});
}

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

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) {

    inp=x;

	for(int i=0;i<x.size();i++)
        there[i].insert(0);

	for(int i=0;i<y.size();i++)
    {
        //cout<<"line: "<<l[i]<<" "<<r[i]<<" "<<y[i]<<endl;

        for(int j=l[i];j<=r[i];j++)
            if(h[j]>=y[i])
            {
                //cout<<"push "<<j<<" h= "<<y[i]<<endl;

                there[j].insert(y[i]);
                noted[i].insert(j);
            }
    }

    int pointer=0;

    for(int i=0;i<x.size();i++)
    {
        for(auto w:there[i])
        {
            id[i][w]=pointer;

            //cout<<"id "<<i<<" "<<w<<" -> "<<pointer<<endl;

            pointer++;
        }
    }

    //cout<<"towers: "<<endl;

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

        for(auto w:there[i])
        {
            if(w)
            {
                add_edge(i,prv,i,w);
            }

            prv=w;
        }
    }

    //cout<<"---"<<endl;

    for(int i=0;i<y.size();i++)
    {
        //cout<<"i= "<<i<<"---"<<endl;

        int prv=-1;

        for(auto w:noted[i])
        {
            if(prv!=-1)
            {
                add_edge(prv,y[i],w,y[i]);
            }

            prv=w;
        }

    }

    /*
    cout<<"there: "<<endl;
    for(int i=0;i<x.size();i++)
    {
        cout<<i<<" -> ";for(auto j:there[i])cout<<j<<" ";cout<<endl;
    }
    */

    for(int i=0;i<=pointer;i++)
        dist.push_back(-1);

    pq.push({0,id[s][0]});

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

        tp.first=-tp.first;

        if(dist[tp.second]!=-1)continue;

        dist[tp.second]=tp.first;

        //cout<<"dist: "<<tp.second<<" -> "<<tp.first<<endl;

        for(auto w:adj[tp.second])
            pq.push({-(tp.first+w.second),w.first});
    }

    return dist[id[g][0]];
}
/*
int main() {
	int n, m;
	assert(2 == scanf("%d%d", &n, &m));
	vector<int> x(n), h(n);
	for (int i = 0; i < n; i++)
		assert(2 == scanf("%d%d", &x[i], &h[i]));
	vector<int> l(m), r(m), y(m);
	for (int i = 0; i < m; i++)
		assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
	int s, g;
	assert(2 == scanf("%d%d", &s, &g));
	fclose(stdin);

	long long result = min_distance(x, h, l, r, y, s, g);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}
*/

컴파일 시 표준 에러 (stderr) 메시지

walk.cpp: In function 'void add_edge(int, int, int, int)':
walk.cpp:27:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     while(adj.size()<=p)adj.push_back({});
      |           ~~~~~~~~~~^~~
walk.cpp:28:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |     while(adj.size()<=q)adj.push_back({});
      |           ~~~~~~~~~~^~~
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:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0;i<x.size();i++)
      |              ~^~~~~~~~~
walk.cpp:43:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i=0;i<y.size();i++)
      |              ~^~~~~~~~~
walk.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
walk.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
walk.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0;i<y.size();i++)
      |                 ~^~~~~~~~~

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