Submission #226580

#	Time	Username	Problem	Language	Result	Execution time	Memory
226580		AaronNaidu	Sky Walking (IOI19_walk)	C++14	10 / 100	154 ms	34284 KiB

walk

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

map<pair<int, int>, int> posOf;
int counter = 0;
vector<pair<int, int> > graph[100001];
vector<pair<int, int> > intersections;
pair<int, int> pairAt[100001];
ll dists[100001];
bool visited[100001];
priority_queue<pair<ll, ll> > q;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
    for (auto i : x)
    {
        posOf.insert({{i, 0}, counter});
        intersections.push_back({i, 0});
        pairAt[counter] = {i, 0};
        counter++;
    }
    for (int i = 0; i < l.size(); i++)
    {
        //cout << "Going from " << l[i] << " to " << r[i] << "\n";
        //cout << "Start with " << l[i] << "\n";
        int prevBuild = l[i];
        if (posOf.find({x[l[i]], y[i]}) == posOf.end())
        {
            posOf.insert({{x[l[i]], y[i]}, counter});
            intersections.push_back({x[l[i]], y[i]});
            pairAt[counter] = {x[l[i]], y[i]};
            counter++;
        }
        for (int j = l[i] + 1; j <= r[i]; j++)
        {
            //cout << "Now doing " << j;
            if (h[j] >= y[i])
            {
                if (posOf.find({x[j], y[i]}) == posOf.end())
                {
                    //cout << "Inserting point " << x[l[j]] << " " << y[i] << " as " << counter << "\n";
                    posOf.insert({{x[j], y[i]}, counter});
                    pairAt[counter] = {x[j], y[i]};
                    intersections.push_back({x[j], y[i]});
                    counter++;
                }
                int fir = posOf.find({x[prevBuild], y[i]})->second;
                int sec = posOf.find({x[j], y[i]})->second;
                int len = abs(x[prevBuild] - x[j]);
                graph[fir].push_back({sec, len});
                graph[sec].push_back({fir, len});
                prevBuild = j;
            }  
        }
    }
    sort(intersections.begin(), intersections.end());
    for (int i = 0; i < intersections.size() - 1; i++)
    {
        if (intersections[i].first == intersections[i+1].first)
        {
            int fir = posOf.find({intersections[i].first, intersections[i].second})->second;
            int sec = posOf.find({intersections[i+1].first, intersections[i+1].second})->second;
            int len = abs(intersections[i].second - intersections[i+1].second);
            graph[fir].push_back({sec, len});
            graph[sec].push_back({fir, len});
        }
        
    }
    //for (int i = 0; i < counter; i++)
    //{
    //   cout << "Point " << i << " is " << pairAt[i].first << " " << pairAt[i].second << "\n";
    //    cout << "It connects to the following:\n";
    //    for (auto j : graph[i])
    //    {
    //        cout << "Point " << j.first << " with length " << j.second << "\n";
    //    }
    //    cout << "\n\n";
    //}
    for (int i = 0; i < 100000; i++)
    {
        dists[i] = 1000000000000;
    }
    
    int startNode = posOf.find({x[s], 0})->second; 
    int endNode = posOf.find({x[g], 0})->second;
    dists[startNode] = 0;
    q.push({0, startNode});
    while (!q.empty())
    {
        int x = q.top().second;
        q.pop();
        if (visited[x])
        {
            continue;
        }
        visited[x] = true;
        for (auto i : graph[x])
        {
            if (!visited[i.first])
            {
                dists[i.first] = min(dists[i.first], dists[x] + i.second);
                q.push({-dists[i.first], i.first});
            }
        }
        if (x == endNode)
        {
            return dists[endNode];
        }
        
    }
    
    return -1;
}

Compilation message (stderr)

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < l.size(); i++)
                     ~~^~~~~~~~~~
walk.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < intersections.size() - 1; i++)
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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