oj.uz

Submission #409665

# Submission time Handle Problem Language Result Execution time Memory
409665 2021-05-21T10:19:49 Z MKopchev Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 701644 KB 
#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;
}
*/

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14284 KB Output is correct
2 Correct 10 ms 14404 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 9 ms 14392 KB Output is correct
5 Correct 10 ms 14532 KB Output is correct
6 Correct 10 ms 14536 KB Output is correct
7 Correct 10 ms 14516 KB Output is correct
8 Correct 10 ms 14412 KB Output is correct
9 Correct 9 ms 14412 KB Output is correct
10 Correct 10 ms 14540 KB Output is correct
11 Correct 9 ms 14412 KB Output is correct
12 Correct 9 ms 14412 KB Output is correct
13 Correct 9 ms 14424 KB Output is correct
14 Correct 9 ms 14412 KB Output is correct
15 Correct 9 ms 14360 KB Output is correct
16 Correct 11 ms 14356 KB Output is correct
17 Correct 11 ms 14540 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14284 KB Output is correct
2 Correct 9 ms 14304 KB Output is correct
3 Correct 1973 ms 188532 KB Output is correct
4 Correct 1287 ms 205732 KB Output is correct
5 Correct 878 ms 181608 KB Output is correct
6 Correct 2271 ms 163968 KB Output is correct
7 Correct 842 ms 181820 KB Output is correct
8 Correct 2623 ms 234300 KB Output is correct
9 Correct 996 ms 179056 KB Output is correct
10 Correct 2089 ms 282916 KB Output is correct
11 Correct 753 ms 110224 KB Output is correct
12 Correct 382 ms 87776 KB Output is correct
13 Correct 1587 ms 243860 KB Output is correct
14 Execution timed out 4056 ms 36100 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 35100 KB Output is correct
2 Execution timed out 4062 ms 701644 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 35100 KB Output is correct
2 Execution timed out 4062 ms 701644 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14284 KB Output is correct
2 Correct 10 ms 14404 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 9 ms 14392 KB Output is correct
5 Correct 10 ms 14532 KB Output is correct
6 Correct 10 ms 14536 KB Output is correct
7 Correct 10 ms 14516 KB Output is correct
8 Correct 10 ms 14412 KB Output is correct
9 Correct 9 ms 14412 KB Output is correct
10 Correct 10 ms 14540 KB Output is correct
11 Correct 9 ms 14412 KB Output is correct
12 Correct 9 ms 14412 KB Output is correct
13 Correct 9 ms 14424 KB Output is correct
14 Correct 9 ms 14412 KB Output is correct
15 Correct 9 ms 14360 KB Output is correct
16 Correct 11 ms 14356 KB Output is correct
17 Correct 11 ms 14540 KB Output is correct
18 Correct 9 ms 14284 KB Output is correct
19 Correct 9 ms 14304 KB Output is correct
20 Correct 1973 ms 188532 KB Output is correct
21 Correct 1287 ms 205732 KB Output is correct
22 Correct 878 ms 181608 KB Output is correct
23 Correct 2271 ms 163968 KB Output is correct
24 Correct 842 ms 181820 KB Output is correct
25 Correct 2623 ms 234300 KB Output is correct
26 Correct 996 ms 179056 KB Output is correct
27 Correct 2089 ms 282916 KB Output is correct
28 Correct 753 ms 110224 KB Output is correct
29 Correct 382 ms 87776 KB Output is correct
30 Correct 1587 ms 243860 KB Output is correct
31 Execution timed out 4056 ms 36100 KB Time limit exceeded
32 Halted 0 ms 0 KB -