Submission #281754

#	Time	Username	Problem	Language	Result	Execution time	Memory
281754		stoyan_malinin	Sky Walking (IOI19_walk)	C++14	0 / 100	224 ms	53088 KiB

walk

#include "walk.h"
//#include "grader.cpp"

#include <set>
#include <map>
#include <queue>
#include <vector>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

const int MAXN = 1e5 + 5;
const int inf = 1e9 + 5;

struct Tower
{
    int x, y;

    Tower(){}
    Tower(int x, int y)
    {
        this->x = x;
        this->y = y;
    }
};

struct Bridge
{
    int y;
    int x1, x2;

    Bridge(){}
    Bridge(int x1, int x2, int y)
    {
        this->x1 = x1;
        this->x2 = x2;
        this->y = y;
    }
};

int s, g;
vector <Tower> towers;
vector <Bridge> bridges;

long long solveSubtask2()
{
    struct Event
    {
        int pos;
        int type;

        Tower towerInfo;

        int bridgeInd;
        Bridge bridgeInfo;

        Event(){}
        Event(int pos, int type, Tower towerInfo)
        {
            this->pos = pos;
            this->type = type;
            this->towerInfo = towerInfo;
        }
        Event(int pos, int type, Bridge bridgeInfo, int bridgeInd)
        {
            this->pos = pos;
            this->type = type;
            this->bridgeInd = bridgeInd;
            this->bridgeInfo = bridgeInfo;
        }
    };

    struct Grid
    {
        map <int, set <int>> horizontal, vertical;
        map <pair <int, int>, pair <int, int>> hAdj;

        void addPoint(int x, int y)
        {
            vertical[x].insert(y);
            horizontal[y].insert(x);

            hAdj[{x, y}] = {-1, inf};
        }

        pair <int, int> horizontalAdj(int x, int y)
        {
            pair <int, int> out = hAdj[{x, y}];
            if(out.second==inf) out.second = -1;

            return out;
        }

        pair <int, int> verticalAdj(int x, int y)
        {
            set <int> *s = &vertical[x];
            auto it = s->find(y);

            assert(it!=s->end());

            pair <int, int> out = {-1, -1};
            if(it!=s->begin())
            {
                auto it1 = it;it1--;
                out.first = *it1;
            }

            it++;
            if(it!=s->end()) out.second = *it;

            //cout << out.first << " " << out.second << '\n';
            return out;
        }
    };
    Grid welko;

    vector <Event> v;
    for(Tower t: towers)
    {
        v.push_back(Event(t.x, 1, t));
    }
    for(int i = 0;i<bridges.size();i++)
    {
        Bridge b = bridges[i];
        v.push_back(Event(b.x1, 0, b, i));
        v.push_back(Event(b.x2, 2, b, i));
    }
    sort(v.begin(), v.end(),
    [&](Event A, Event B)
    {
        if(A.pos!=B.pos) return A.pos<B.pos;
        return A.type<B.type;
    });

    set <pair <int, int>> ms;
    vector <vector <int>> intersections;

    intersections.resize(bridges.size());
    for(Event e: v)
    {
        if(e.type==0)
        {
            ms.insert({e.bridgeInfo.y, e.bridgeInd});
        }
        else if(e.type==1)
        {
            auto it = ms.upper_bound({e.towerInfo.y, MAXN});
            if(it!=ms.begin())
            {
                it--;
                while(true)
                {
                    //cout << e.towerInfo.x << " -- " << it->first << '\n';

                    welko.addPoint(e.towerInfo.x, it->first);
                    intersections[it->second].push_back(e.towerInfo.x);

                    if(it==ms.begin()) break;
                    it--;
                }
            }
        }
        else if(e.type==2)
        {
            ms.erase({e.bridgeInfo.y, e.bridgeInd});
        }
    }
    for(Tower t: towers)
    {
        welko.addPoint(t.x, 0);
        welko.addPoint(t.x, t.y);
    }

    for(int i = 0;i<bridges.size();i++)
    {
        vector <int> v = intersections[i];
        for(int j = 0;j<v.size();j++)
        {
            if(j!=0)
                welko.hAdj[{v[j], bridges[i].y}].first = max(welko.hAdj[{v[j], bridges[i].y}].first, v[j-1]);
            if(j!=v.size()-1)
                welko.hAdj[{v[j], bridges[i].y}].second = min(welko.hAdj[{v[j], bridges[i].y}].second, v[j+1]);
        }

        //assert(v.size()<=10);
        //cout << i << " -> " << v.size() << '\n';
    }

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

    vector <vector <pair <int, int>>> graph;
    graph.resize(welko.hAdj.size()+5);

    map <pair <int, int>, int> code;
    for(auto item: welko.hAdj)
    {
        code[item.first] = code.size() - 1;
    }
    for(auto item: welko.hAdj)
    {
        pair <int, int> x = item.first;
        int ind = code[x];

        pair <int, int> jump1 = welko.horizontalAdj(x.first, x.second);
        pair <int, int> jump2 = welko.verticalAdj(x.first, x.second);

        if(jump1.first!=-1) graph[ind].push_back({code[{jump1.first, x.second}], (x.first-jump1.first)});
        if(jump1.second!=-1) graph[ind].push_back({code[{jump1.second, x.second}], (jump1.second-x.first)});

        if(jump2.first!=-1) graph[ind].push_back({code[{x.first, jump2.first}], (x.second-jump2.first)});
        if(jump2.second!=-1) graph[ind].push_back({code[{x.first, jump2.second}], (jump2.second-x.second)});
    }
    dist.assign(code.size()+1, -1);

    int start = code[{towers[s].x, 0}];
    int finish = code[{towers[g].x, 0}];

    pq.push({0, start});
    dist[start] = 0;

    while(pq.empty()==false)
    {
        int x = pq.top().second;
        long long d = -pq.top().first;

        //cout << d << " == " << dist[x] << '\n';

        if(x==finish)
        {
            return d;
        }

        pq.pop();
        if(d!=dist[x]) continue;

        //cout << x.first << " " << x.second << " -> " << d << '\n';

        for(pair <int, long long> item: graph[x])
        {
            if(dist[item.first]==-1 || d+item.second<dist[item.first])
            {
                long long newD = d + item.second;

                dist[item.first] = newD;
                pq.push({-newD, item.first});
            }
        }
    }

    return dist[finish];
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int _s, int _g)
{
    s = _s;
    g = _g;
    for(int i = 0;i<x.size();i++)
    {
        towers.push_back(Tower(x[i], h[i]));
    }
    for(int i = 0;i<l.size();i++)
    {
        bridges.push_back(Bridge(x[ l[i] ], x[ r[i] ], y[i]));
    }

    //cout << '\n';
    return solveSubtask2();
}
/*
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5

5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4
*/

Compilation message (stderr)

walk.cpp: In function 'long long int solveSubtask2()':
walk.cpp:125:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bridge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i = 0;i<bridges.size();i++)
      |                   ~^~~~~~~~~~~~~~~
walk.cpp:177:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bridge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for(int i = 0;i<bridges.size();i++)
      |                   ~^~~~~~~~~~~~~~~
walk.cpp:180:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |         for(int j = 0;j<v.size();j++)
      |                       ~^~~~~~~~~
walk.cpp:184:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |             if(j!=v.size()-1)
      |                ~^~~~~~~~~~~~
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:261:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  261 |     for(int i = 0;i<x.size();i++)
      |                   ~^~~~~~~~~
walk.cpp:265:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  265 |     for(int i = 0;i<l.size();i++)
      |                   ~^~~~~~~~~

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