oj.uz

답안 #416370

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
416370 2021-06-02T10:39:17 Z idk321 Sky Walking (IOI19_walk) C++17
24 / 100
 1091 ms 344208 KB 
#include "walk.h"

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


const int M = 2000005;
const int N = 100005;
const ll INF = 2000000000000000000LL;
vector<array<int, 2>> adj[M];
vector<array<int, 2>> isAt[N];

int cnode = 0;


///usr/include/c++/10/bits/stl_heap.h|209|error: ‘bool Comparator::operator()(const std::__debug::array<long long int, 2>&, const std::__debug::array<long long int, 2>&) const’ is private within this context|

struct Comparator
{

    bool operator() (const array<ll, 2>& ar1, const array<ll, 2>& ar2) const
    {
        return tie(ar1[1], ar1[0]) > tie(ar2[1], ar2[0]);
    }
};

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) {

    int snode = -1;
    int gnode = -1;
    for (int i = 0; i < x.size(); i++)
    {
        isAt[i].push_back({cnode, 0});
        if (i == s)
        {
            snode = cnode;
        }
        if (i == g)
        {
            gnode = cnode;
        }
        cnode++;
    }



    vector<array<int, 2>> byHeight;
    for (int i = 0; i < l.size(); i++)
    {
        byHeight.push_back({y[i], i});
    }
    sort(byHeight.begin(), byHeight.end());

    set<int> ok;

    for (int i = 0; i < x.size(); i++) ok.insert(i);

    for (int ci = 0; ci < l.size(); ci++)
    {
        int i = byHeight[ci][1];
        int prev = -1;
        for (auto it = ok.lower_bound(l[i]); it != ok.end() && *it <= r[i]; )
        {
            int j = *it;
            if (h[j] >= y[i])
            {

                adj[cnode].push_back({isAt[j].back()[0], abs(isAt[j].back()[1] - y[i])});
                adj[isAt[j].back()[0]].push_back({cnode, abs(isAt[j].back()[1] - y[i])});


                isAt[j].push_back({cnode, y[i]});
                if (prev != -1)
                {
                    adj[cnode].push_back({cnode - 1, x[j] - x[prev]});
                    adj[cnode - 1].push_back({cnode, x[j] - x[prev]});
                }
                prev = j;
                cnode++;
                it++;
            } else
            {
                it = ok.erase(it);
            }
        }
    }

    priority_queue<array<ll, 2>, vector<array<ll, 2>>, Comparator> pq;

    pq.push({snode, 0});

    vector<ll> dist(M, INF);
    while (!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();
        if (dist[cur[0]] != INF) continue;
        dist[cur[0]] = cur[1];



        for (auto next : adj[cur[0]])
        {
            if (dist[next[0]] == INF)
            {

                pq.push({next[0], next[1] + cur[1]});
            }
        }
    }



    if (dist[gnode] == INF) return -1;
	return dist[gnode];
}

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:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < x.size(); i++)
      |                     ~~^~~~~~~~~~
walk.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < l.size(); i++)
      |                     ~~^~~~~~~~~~
walk.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < x.size(); i++) ok.insert(i);
      |                     ~~^~~~~~~~~~
walk.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int ci = 0; ci < l.size(); ci++)
      |                      ~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 65220 KB Output is correct
2 Correct 39 ms 65316 KB Output is correct
3 Correct 38 ms 65228 KB Output is correct
4 Correct 39 ms 65236 KB Output is correct
5 Correct 39 ms 65284 KB Output is correct
6 Correct 39 ms 65188 KB Output is correct
7 Correct 40 ms 65280 KB Output is correct
8 Correct 38 ms 65224 KB Output is correct
9 Correct 39 ms 65260 KB Output is correct
10 Correct 37 ms 65264 KB Output is correct
11 Correct 38 ms 65228 KB Output is correct
12 Correct 38 ms 65216 KB Output is correct
13 Correct 38 ms 65288 KB Output is correct
14 Correct 38 ms 65248 KB Output is correct
15 Correct 38 ms 65336 KB Output is correct
16 Correct 44 ms 65188 KB Output is correct
17 Correct 37 ms 65244 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 65228 KB Output is correct
2 Correct 38 ms 65216 KB Output is correct
3 Correct 662 ms 112308 KB Output is correct
4 Correct 923 ms 123944 KB Output is correct
5 Correct 528 ms 113520 KB Output is correct
6 Correct 479 ms 108464 KB Output is correct
7 Correct 521 ms 113500 KB Output is correct
8 Correct 802 ms 124044 KB Output is correct
9 Correct 629 ms 113388 KB Output is correct
10 Correct 1091 ms 139168 KB Output is correct
11 Correct 513 ms 94680 KB Output is correct
12 Correct 417 ms 94908 KB Output is correct
13 Correct 997 ms 133740 KB Output is correct
14 Correct 271 ms 88252 KB Output is correct
15 Correct 323 ms 91996 KB Output is correct
16 Correct 353 ms 91664 KB Output is correct
17 Correct 351 ms 90680 KB Output is correct
18 Correct 220 ms 88776 KB Output is correct
19 Correct 43 ms 66356 KB Output is correct
20 Correct 114 ms 76896 KB Output is correct
21 Correct 354 ms 90232 KB Output is correct
22 Correct 445 ms 96632 KB Output is correct
23 Correct 272 ms 93332 KB Output is correct
24 Correct 389 ms 93808 KB Output is correct
25 Correct 380 ms 90796 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 75064 KB Output is correct
2 Runtime error 704 ms 344208 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 75064 KB Output is correct
2 Runtime error 704 ms 344208 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 65220 KB Output is correct
2 Correct 39 ms 65316 KB Output is correct
3 Correct 38 ms 65228 KB Output is correct
4 Correct 39 ms 65236 KB Output is correct
5 Correct 39 ms 65284 KB Output is correct
6 Correct 39 ms 65188 KB Output is correct
7 Correct 40 ms 65280 KB Output is correct
8 Correct 38 ms 65224 KB Output is correct
9 Correct 39 ms 65260 KB Output is correct
10 Correct 37 ms 65264 KB Output is correct
11 Correct 38 ms 65228 KB Output is correct
12 Correct 38 ms 65216 KB Output is correct
13 Correct 38 ms 65288 KB Output is correct
14 Correct 38 ms 65248 KB Output is correct
15 Correct 38 ms 65336 KB Output is correct
16 Correct 44 ms 65188 KB Output is correct
17 Correct 37 ms 65244 KB Output is correct
18 Correct 38 ms 65228 KB Output is correct
19 Correct 38 ms 65216 KB Output is correct
20 Correct 662 ms 112308 KB Output is correct
21 Correct 923 ms 123944 KB Output is correct
22 Correct 528 ms 113520 KB Output is correct
23 Correct 479 ms 108464 KB Output is correct
24 Correct 521 ms 113500 KB Output is correct
25 Correct 802 ms 124044 KB Output is correct
26 Correct 629 ms 113388 KB Output is correct
27 Correct 1091 ms 139168 KB Output is correct
28 Correct 513 ms 94680 KB Output is correct
29 Correct 417 ms 94908 KB Output is correct
30 Correct 997 ms 133740 KB Output is correct
31 Correct 271 ms 88252 KB Output is correct
32 Correct 323 ms 91996 KB Output is correct
33 Correct 353 ms 91664 KB Output is correct
34 Correct 351 ms 90680 KB Output is correct
35 Correct 220 ms 88776 KB Output is correct
36 Correct 43 ms 66356 KB Output is correct
37 Correct 114 ms 76896 KB Output is correct
38 Correct 354 ms 90232 KB Output is correct
39 Correct 445 ms 96632 KB Output is correct
40 Correct 272 ms 93332 KB Output is correct
41 Correct 389 ms 93808 KB Output is correct
42 Correct 380 ms 90796 KB Output is correct
43 Correct 135 ms 75064 KB Output is correct
44 Runtime error 704 ms 344208 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -