oj.uz

Submission #281738

# Submission time Handle Problem Language Result Execution time Memory
281738 2020-08-23T11:57:55 Z stoyan_malinin Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 355420 KB 
#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(ms.find({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]);
        }

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

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

    pq.push({0, {towers[s].x, 0}});
    dist[{towers[s].x, 0}] = 0;

    function <void(int, int, long long)> updateNode = [&](int x, int y, long long newD)
    {
        if(dist.count({x, y})==false || newD<dist[{x, y}])
        {
            dist[{x, y}] = newD;
            pq.push({-newD, {x, y}});
        }
    };

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

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

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

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

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

        if(jump1.first!=-1) updateNode(jump1.first, x.second, d+(x.first-jump1.first));
        if(jump1.second!=-1) updateNode(jump1.second, x.second, d+(jump1.second-x.first));

        if(jump2.first!=-1) updateNode(x.first, jump2.first, d+(x.second-jump2.first));
        if(jump2.second!=-1) updateNode(x.first, jump2.second, d+(jump2.second-x.second));
    }

    return ((dist.count({towers[g].x, 0})==true)?dist[{towers[g].x, 0}]:-1);
}

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

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:235:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  235 |     for(int i = 0;i<x.size();i++)
      |                   ~^~~~~~~~~
walk.cpp:239:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |     for(int i = 0;i<l.size();i++)
      |                   ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 512 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 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 512 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 0 ms 256 KB Output is correct
3 Execution timed out 4107 ms 181084 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 24676 KB Output is correct
2 Execution timed out 4117 ms 355420 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 24676 KB Output is correct
2 Execution timed out 4117 ms 355420 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 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 512 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 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Execution timed out 4107 ms 181084 KB Time limit exceeded
21 Halted 0 ms 0 KB -