oj.uz

Submission #448051

# Submission time Handle Problem Language Result Execution time Memory
448051 2021-07-28T16:40:51 Z blue Sky Walking (IOI19_walk) C++17
10 / 100
 43 ms 8832 KB 
#include "walk.h"
#include <vector>
#include <set>
using namespace std;

const long long INF = 1'000'000'000'000'000'000LL;

vector<int> edge[10000];
vector<long long> wt[10000];
vector<long long> src_dist(10000, INF);

void add_edge(int u, int v, long long w)
{
    edge[u].push_back(v);
    wt[u].push_back(w);

    edge[v].push_back(u);
    wt[v].push_back(w);
}

long long abs_diff(long long p, long long q)
{
    return max(p-q, q-p);
}

struct pos
{
    int i;
};

bool operator < (pos X, pos Y)
{
    if(src_dist[X.i] == src_dist[Y.i]) return X.i < Y.i;
    return src_dist[X.i] < src_dist[Y.i];
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
    int N = x.size();
    int M1 = y.size();

    for(int i = 0; i < N; i++)
    {
        l.push_back(i);
        r.push_back(i);
        y.push_back(0);
    }

    int M = y.size();

    for(int i = 0; i < N; i++)
    {
        for(int j1 = 0; j1 < M; j1++)
        {
            if(i < l[j1] || r[j1] < i || h[i] < y[j1]) continue;
            for(int j2 = j1+1; j2 < M; j2++)
            {
                if(i < l[j2] || r[j2] < i || h[i] < y[j2]) continue;
                add_edge(M*i + j1, M*i + j2, abs_diff(y[j1], y[j2]));
            }
        }
    }

    for(int i1 = 0; i1 < N; i1++)
    {
        for(int i2 = i1+1; i2 < N; i2++)
        {
            for(int j = 0; j < M; j++)
            {
                if(i1 < l[j] || r[j] < i1 || h[i1] < y[j]) continue;
                if(i2 < l[j] || r[j] < i2 || h[i2] < y[j]) continue;
                add_edge(M*i1 + j, M*i2 + j, x[i2] - x[i1]);
            }
        }
    }

    set<pos> tbv;

    int src = M*s + (M1+s);
    int dst = M*g + (M1+g);

    src_dist[src] = 0;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            tbv.insert(pos{M*i + j});

    while(!tbv.empty())
    {
        int u = tbv.begin()->i;
        tbv.erase(tbv.begin());

        for(int e = 0; e < edge[u].size(); e++)
        {
            int v = edge[u][e];
            long long w = wt[u][e];

            if(src_dist[v] > src_dist[u] + w)
            {
                tbv.erase(pos{v});
                src_dist[v] = src_dist[u] + w;
                tbv.insert(pos{v});
            }
        }
    }

    if(src_dist[M*g + (M1 + g)] >= INF) return -1;
    else return src_dist[M*g + (M1 + g)];
}

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:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for(int e = 0; e < edge[u].size(); e++)
      |                        ~~^~~~~~~~~~~~~~~~
walk.cpp:80:9: warning: unused variable 'dst' [-Wunused-variable]
   80 |     int dst = M*g + (M1+g);
      |         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 4 ms 1356 KB Output is correct
6 Correct 4 ms 1356 KB Output is correct
7 Correct 4 ms 1336 KB Output is correct
8 Correct 3 ms 1228 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 5 ms 1596 KB Output is correct
11 Correct 2 ms 972 KB Output is correct
12 Correct 2 ms 1080 KB Output is correct
13 Correct 2 ms 972 KB Output is correct
14 Correct 2 ms 936 KB Output is correct
15 Correct 1 ms 844 KB Output is correct
16 Correct 2 ms 952 KB Output is correct
17 Correct 5 ms 1612 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Runtime error 43 ms 8832 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 4364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 4364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 4 ms 1356 KB Output is correct
6 Correct 4 ms 1356 KB Output is correct
7 Correct 4 ms 1336 KB Output is correct
8 Correct 3 ms 1228 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 5 ms 1596 KB Output is correct
11 Correct 2 ms 972 KB Output is correct
12 Correct 2 ms 1080 KB Output is correct
13 Correct 2 ms 972 KB Output is correct
14 Correct 2 ms 936 KB Output is correct
15 Correct 1 ms 844 KB Output is correct
16 Correct 2 ms 952 KB Output is correct
17 Correct 5 ms 1612 KB Output is correct
18 Correct 1 ms 716 KB Output is correct
19 Correct 1 ms 716 KB Output is correct
20 Runtime error 43 ms 8832 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -