oj.uz

Submission #298692

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

typedef long long ll;

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

ll INF = 1e18;

ll dijkstra(int a, int b){
    int n = adjlist.size();
    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(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:46:9: warning: unused variable 'numnodes' [-Wunused-variable]
   46 |     int numnodes = 0;
      |         ^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Execution timed out 4064 ms 13772 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2011 ms 10400 KB Output is correct
2 Execution timed out 4038 ms 13592 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2011 ms 10400 KB Output is correct
2 Execution timed out 4038 ms 13592 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Execution timed out 4064 ms 13772 KB Time limit exceeded
21 Halted 0 ms 0 KB -