oj.uz

Submission #298694

# Submission time Handle Problem Language Result Execution time Memory
298694 2020-09-13T19:57:52 Z eohomegrownapps Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 246548 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<pair<ll,int>> adjlist[10000000]; // weight, node

ll INF = 1e18;

ll dijkstra(int n, int a, int b){
    vector<ll> distance(n,INF);
    distance[a]=0;
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    pq.push({0,a});
    while (pq.size()>0){
        auto f = pq.top();
        pq.pop();
        if (f.first>distance[f.second]){continue;}
        for (auto p : adjlist[f.second]){
            if (distance[f.second]+p.first<distance[p.second]){
                distance[p.second]=distance[f.second]+p.first;
                pq.push({distance[p.second],p.second});
            }
        }
    }
    return (distance[b]==INF)?-1:distance[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) {
	// x - horizontal distance
    int n = x.size();
    vector<int> coords = x;
    sort(coords.begin(),coords.end());
    vector<int> heights(n);
    for (int i = 0; i<n; i++){
        heights[i]=h[lower_bound(coords.begin(),coords.end(),x[i])-coords.begin()];
    }
    int m = l.size();
    vector<int> inds(m);
    for (int i = 0; i<m; i++){
        inds[i]=i;
    }
    sort(inds.begin(),inds.end(),[y](int a, int b){return y[a]<y[b];});
    int numnodes = 0;
    vector<int> lastnode(n);
    vector<int> lastheight(n,0);
    //adjlist.resize(n);
    for (int i = 0; i<n; i++){
        lastnode[i]=i;
    }

    int curnode = n;
    for (int i = 0; i<m; i++){
        // process skywalk inds[i]
        int lc = l[inds[i]];
        int rc = r[inds[i]];
        //cout<<"process "<<lc<<' '<<rc<<'\n';
        int prev = -1;
        for (int j = lc; j<=rc; j++){
            //cout<<"heights: "<<heights[j]<<'\n';
            // link j to below
            if (heights[j]<y[inds[i]]){continue;}
            if (lastheight[j]!=y[inds[i]]){
                //cout<<"connect "<<curnode<<' '<<lastnode[j]<<'\n';
                //adjlist.push_back(vector<pair<ll,int>>());
                adjlist[curnode].push_back({y[inds[i]]-lastheight[j],lastnode[j]});
                adjlist[lastnode[j]].push_back({y[inds[i]]-lastheight[j],curnode});
                lastnode[j]=curnode;
                lastheight[j]=y[inds[i]];
                curnode++;
            }
            // link j to left
            if (j!=lc){
                //cout<<"connect "<<lastnode[j]<<' '<<lastnode[prev]<<'\n';
                adjlist[lastnode[j]].push_back({x[j]-x[prev],lastnode[prev]});
                adjlist[lastnode[prev]].push_back({x[j]-x[prev],lastnode[j]});
            }
            prev = j;
        }
    }
    return dijkstra(curnode,s,g);
}

Compilation message

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:45:9: warning: unused variable 'numnodes' [-Wunused-variable]
   45 |     int numnodes = 0;
      |         ^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 235128 KB Output is correct
2 Correct 158 ms 235128 KB Output is correct
3 Correct 158 ms 235128 KB Output is correct
4 Correct 157 ms 235128 KB Output is correct
5 Correct 158 ms 235128 KB Output is correct
6 Correct 158 ms 235128 KB Output is correct
7 Correct 158 ms 235128 KB Output is correct
8 Correct 158 ms 235256 KB Output is correct
9 Correct 160 ms 235128 KB Output is correct
10 Correct 161 ms 235256 KB Output is correct
11 Correct 161 ms 235264 KB Output is correct
12 Correct 160 ms 235256 KB Output is correct
13 Correct 160 ms 235128 KB Output is correct
14 Correct 158 ms 235328 KB Output is correct
15 Correct 157 ms 235348 KB Output is correct
16 Correct 160 ms 235384 KB Output is correct
17 Correct 159 ms 235256 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 235128 KB Output is correct
2 Correct 157 ms 235128 KB Output is correct
3 Execution timed out 4081 ms 245960 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2154 ms 242756 KB Output is correct
2 Execution timed out 4077 ms 246548 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2154 ms 242756 KB Output is correct
2 Execution timed out 4077 ms 246548 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 235128 KB Output is correct
2 Correct 158 ms 235128 KB Output is correct
3 Correct 158 ms 235128 KB Output is correct
4 Correct 157 ms 235128 KB Output is correct
5 Correct 158 ms 235128 KB Output is correct
6 Correct 158 ms 235128 KB Output is correct
7 Correct 158 ms 235128 KB Output is correct
8 Correct 158 ms 235256 KB Output is correct
9 Correct 160 ms 235128 KB Output is correct
10 Correct 161 ms 235256 KB Output is correct
11 Correct 161 ms 235264 KB Output is correct
12 Correct 160 ms 235256 KB Output is correct
13 Correct 160 ms 235128 KB Output is correct
14 Correct 158 ms 235328 KB Output is correct
15 Correct 157 ms 235348 KB Output is correct
16 Correct 160 ms 235384 KB Output is correct
17 Correct 159 ms 235256 KB Output is correct
18 Correct 158 ms 235128 KB Output is correct
19 Correct 157 ms 235128 KB Output is correct
20 Execution timed out 4081 ms 245960 KB Time limit exceeded
21 Halted 0 ms 0 KB -