oj.uz

Submission #448070

# Submission time Handle Problem Language Result Execution time Memory
448070 2021-07-28T17:18:52 Z blue Sky Walking (IOI19_walk) C++17
15 / 100
 1539 ms 49988 KB 
#include "walk.h"
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 100'000;
const int maxM = 100'000;
const int lg = 19;
const long long INF = 1'000'000'000'000'000'000LL;

int N;
vector<int> X;
vector<int> H;

int M;
vector<int> L;
vector<int> R;
vector<int> Y;

const int S = maxM;
const int G = maxM + 1;
const int no_skywalk = -1;






bool skywalk_comp(int p, int q) //compare skywalks by height
{
    if(p == no_skywalk) return 1; //-1 -> height = -INF
    else if(q == no_skywalk) return 0;
    else if(Y[p] == Y[q]) return p < q;
    else return Y[p] < Y[q];
}

int max_skywalk(int p, int q)
{
    if(skywalk_comp(p, q)) return q;
    else return p;
}



struct segtree
{
    int l;
    int r;
    vector<int> w; //skywalks sorted by height

    segtree* left = NULL;
    segtree* right = NULL;


    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;

        if(l == r) return;

        int m = (l+r)/2;

        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    void add_skywalk(int i) //over L[i] to R[i];
    {
        if(R[i] < l || r < L[i]) return;
        else if(L[i] <= l && r <= R[i])
        {
            w.push_back(i);
        }
        else
        {
            left->add_skywalk(i);
            right->add_skywalk(i);
        }
    }

    void sort_skywalks()
    {
        sort(w.begin(), w.end(), skywalk_comp);

        if(l != r)
        {
            left->sort_skywalks();
            right->sort_skywalks();
        }
    }

    int locate_lower(int I, int J) //building i, skywalk j
    {
        //if(I < L[J] || R[J] < I) return -1; //guaranteed;
        if(I < l || r < I) return no_skywalk;
        else
        {
            int ind = -1;
            for(int bit = lg; bit >= 0; bit--)
            {
                if(ind + (1 << bit) >= w.size()) continue;
                if(!skywalk_comp(w[ind + (1 << bit)], J)) continue;
                ind += (1 << bit);
            }

            // if(ind != -1 && w[ind] == I) ind--;

            int curr_walk = (ind == -1) ? no_skywalk : w[ind];

            int lower_walk;
            if(l == r) lower_walk = no_skywalk;
            else lower_walk = max_skywalk(left->locate_lower(I, J), right->locate_lower(I, J));

            return max_skywalk(curr_walk, lower_walk);
        }
    }

    // int locate_higher(int I, int J) //building i, skywalk j
    // {
    //     //if(I < L[J] || R[J] < I) return -1; //guaranteed;
    //     if(I < l || r < I) return no_skywalk;
    //     else
    //     {
    //         int ind = -1;
    //         for(int bit = lg; bit >= 0; bit--)
    //         {
    //             if(ind + (1 << bit) >= w.size()) continue;
    //             if(!skywalk_comp(w[ind + (1 << bit)], J)) continue;
    //             ind += (1 << bit);
    //         }
    //     }
    // }
};




vector<int> edge[maxM + 3];
vector<long long> dist[maxM + 3];

void add_edge(int u, int v, long long w)
{
    // cerr << "add edge " << u << ' ' << v << ' ' << w << '\n';
    edge[u].push_back(v);
    dist[u].push_back(w);
}

vector<long long> distS(maxM + 3, INF);

struct pos
{
    int i;
};

bool operator < (pos A, pos B)
{
    if(distS[A.i] == distS[B.i]) return A.i < B.i;
    return distS[A.i] < distS[B.i];
}



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

    M = l.size();
    L = l;
    R = r;
    Y = y;

    //source = 0, destination = n-1
    segtree ST(0, N-1);
    for(int j = 0; j < M; j++)
        ST.add_skywalk(j);

    ST.sort_skywalks();


    for(int j = 0; j < M; j++)
    {
        // cerr << "j = " << j << ' ' << L[j] << ' ' << R[j] << '\n';
        int l_w = ST.locate_lower(L[j], j);
        if(l_w != no_skywalk)
        {
            add_edge(l_w, j, X[ R[j] ] - X[ L[j] ] + Y[j] - Y[l_w]);
        }

        int r_w = ST.locate_lower(R[j], j);
        // cerr << "locate lower " << R[j] << ' ' << j << ' ' << r_w << '\n';
        if(r_w != no_skywalk)
        {
            add_edge(j, r_w, X[ R[r_w] ] - X[ R[j] ] + Y[j] - Y[r_w]);
        }

        if(L[j] == 0)
            add_edge(S, j, X[ R[j] ] - X[0] + Y[j]);

        if(R[j] == N-1)
            add_edge(j, G, Y[j]);
    }


    distS[S] = 0;
    set<pos> tbv;
    for(int j = 0; j < M; j++) tbv.insert(pos{j});
    tbv.insert(pos{S});
    tbv.insert(pos{G});

    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 wt = dist[u][e];

            if(distS[v] > distS[u] + wt)
            {
                tbv.erase(pos{v});
                // cerr << u << ' ' << v << ' ' << distS[u] + wt << '\n';
                distS[v] = distS[u] + wt;
                tbv.insert(pos{v});
            }
        }
    }

    // for(int j = 0; j < M; j++) cerr << j << ' ' << distS[j] << '\n';
    // cerr << "S " << distS[S] << '\n';
    // cerr << "G " << distS[G] << '\n';

    // for(int j = 0; j < M; j++) cerr << "dist " << j << " = " << distS[j] << '\n';

    if(distS[G] == INF) distS[G] = -1;

    return distS[G];
}

Compilation message

walk.cpp: In member function 'int segtree::locate_lower(int, int)':
walk.cpp:108:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                 if(ind + (1 << bit) >= w.size()) continue;
      |                    ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
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:224:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |         for(int e = 0; e < edge[u].size(); e++)
      |                        ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 15080 KB Output is correct
2 Correct 752 ms 25604 KB Output is correct
3 Correct 1044 ms 29492 KB Output is correct
4 Correct 1253 ms 49200 KB Output is correct
5 Correct 1266 ms 49232 KB Output is correct
6 Correct 1539 ms 49988 KB Output is correct
7 Correct 428 ms 36524 KB Output is correct
8 Correct 516 ms 43448 KB Output is correct
9 Correct 1292 ms 49072 KB Output is correct
10 Correct 576 ms 43184 KB Output is correct
11 Correct 21 ms 13900 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 15080 KB Output is correct
2 Correct 752 ms 25604 KB Output is correct
3 Correct 1044 ms 29492 KB Output is correct
4 Correct 1253 ms 49200 KB Output is correct
5 Correct 1266 ms 49232 KB Output is correct
6 Correct 1539 ms 49988 KB Output is correct
7 Correct 428 ms 36524 KB Output is correct
8 Correct 516 ms 43448 KB Output is correct
9 Correct 1292 ms 49072 KB Output is correct
10 Correct 576 ms 43184 KB Output is correct
11 Correct 21 ms 13900 KB Output is correct
12 Incorrect 973 ms 29412 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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