oj.uz

Submission #416550

# Submission time Handle Problem Language Result Execution time Memory
416550 2021-06-02T15:16:58 Z idk321 Sky Walking (IOI19_walk) C++17
0 / 100
 325 ms 68764 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<int> adj[M];
vector<array<int, 2>> isAt[N];

int cnode = 0;
ll dp[N];


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



    vector<vector<int>> startsAt(x.size());
    vector<vector<int>> endsAt(x.size());

    for (int i = 0; i < l.size(); i++)
    {
        startsAt[l[i]].push_back(i);
        endsAt[r[i]].push_back(i);
    }


    multiset<array<int, 2>> sett;

    vector<int> in(y.size());
    for (int i = 0; i < x.size(); i++)
    {
        for (int j : endsAt[i])
        {
            sett.erase(sett.find({y[j], j}));
        }
        for (int j : startsAt[i])
        {
            sett.insert({y[j], j});
        }

        for (int j : endsAt[i])
        {
            auto it = sett.upper_bound({y[j], -1});
            if (it != sett.end())
            {
                adj[(*it)[1]].push_back(j);
                in[j]++;
            }
            if (it != sett.begin())
            {
                it--;
                adj[(*it)[1]].push_back(j);
                in[j]++;
            }
        }
    }

    for (int i = 0; i <N; i++) dp[i] = INF;


    for (int i : endsAt[x.size() - 1])
    {
        dp[i] = y[i];
    }

    vector<int> noIn;
    for (int i = 0; i < in.size(); i++)
    {
        if (in[i] == 0)
        {
            noIn.push_back(i);
        }
    }

    while (!noIn.empty())
    {
        int cur = noIn.back();
        noIn.pop_back();
        for (int next : adj[cur])
        {
            in[next]--;
            dp[next] = min(dp[cur] + abs(y[cur] - y[next]), dp[next]);
            if (in[next] == 0) noIn.push_back(next);
        }
    }


    int small = 2000000000;
    int ismall = -1;
    for (int i : startsAt[0])
    {
        if (y[i] < small)
        {
            small = y[i];
            ismall = i;
        }
    }

    if (dp[ismall] == INF) return -1;
    return dp[ismall] + y[ismall] + x.back() - x.front();
}

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 50380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 50372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 54748 KB Output is correct
2 Correct 211 ms 56896 KB Output is correct
3 Correct 194 ms 57924 KB Output is correct
4 Correct 262 ms 65876 KB Output is correct
5 Correct 325 ms 66812 KB Output is correct
6 Correct 271 ms 66976 KB Output is correct
7 Correct 139 ms 61660 KB Output is correct
8 Correct 198 ms 68764 KB Output is correct
9 Correct 261 ms 68500 KB Output is correct
10 Correct 160 ms 66128 KB Output is correct
11 Incorrect 44 ms 53444 KB Output isn't correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 54748 KB Output is correct
2 Correct 211 ms 56896 KB Output is correct
3 Correct 194 ms 57924 KB Output is correct
4 Correct 262 ms 65876 KB Output is correct
5 Correct 325 ms 66812 KB Output is correct
6 Correct 271 ms 66976 KB Output is correct
7 Correct 139 ms 61660 KB Output is correct
8 Correct 198 ms 68764 KB Output is correct
9 Correct 261 ms 68500 KB Output is correct
10 Correct 160 ms 66128 KB Output is correct
11 Incorrect 44 ms 53444 KB Output isn't correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 50380 KB Output isn't correct
2 Halted 0 ms 0 KB -