oj.uz

Submission #448087

# Submission time Handle Problem Language Result Execution time Memory
448087 2021-07-28T19:10:32 Z blue Sky Walking (IOI19_walk) C++17
33 / 100
 1016 ms 50008 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];
}

bool skywalk_leq(int p, int q)
{
    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;
}

int min_skywalk(int p, int q)
{
    if(p == no_skywalk) return q;
    else if(q == no_skywalk) return p;
    return p + q - max_skywalk(p, q);
}



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 deeper_walk;
            if(l == r) deeper_walk = no_skywalk;
            else deeper_walk = max_skywalk(left->locate_lower(I, J), right->locate_lower(I, J));

            return max_skywalk(curr_walk, deeper_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_leq(w[ind + (1 << bit)], J)) continue;
                ind += (1 << bit);
            }
            ind++;

            int curr_walk = (ind >= w.size() ? no_skywalk : w[ind]);

            int deeper_walk;
            if(l == r) deeper_walk = no_skywalk;
            else deeper_walk = min_skywalk(left->locate_higher(I, J), right->locate_higher(I, J));

            return min_skywalk(curr_walk, deeper_walk);
        }
    }
};




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 top_walk = ST.locate_higher(R[j], j);
        if(top_walk != no_skywalk)
        {
            // cerr << "t1\n";
            add_edge(j, top_walk, X[ R[top_walk] ] - X[ R[j] ] + Y[top_walk] - Y[j]);
        }

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

        if(L[j] == 0)
        {
            add_edge(S, j, X[ R[j] ] - X[0] + Y[j]);
            // cerr << "S " << j << ' ' << R[j] << ' ' << X[R[j]] << ' ' << X[0] << ' ' << Y[j] << '\n';
        }

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 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 3 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 157 ms 14992 KB Output is correct
2 Correct 486 ms 23224 KB Output is correct
3 Correct 642 ms 26752 KB Output is correct
4 Correct 862 ms 44868 KB Output is correct
5 Correct 820 ms 44708 KB Output is correct
6 Correct 1016 ms 45688 KB Output is correct
7 Correct 316 ms 32836 KB Output is correct
8 Correct 445 ms 39520 KB Output is correct
9 Correct 910 ms 45432 KB Output is correct
10 Correct 491 ms 39988 KB Output is correct
11 Correct 21 ms 13388 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 14992 KB Output is correct
2 Correct 486 ms 23224 KB Output is correct
3 Correct 642 ms 26752 KB Output is correct
4 Correct 862 ms 44868 KB Output is correct
5 Correct 820 ms 44708 KB Output is correct
6 Correct 1016 ms 45688 KB Output is correct
7 Correct 316 ms 32836 KB Output is correct
8 Correct 445 ms 39520 KB Output is correct
9 Correct 910 ms 45432 KB Output is correct
10 Correct 491 ms 39988 KB Output is correct
11 Correct 21 ms 13388 KB Output is correct
12 Correct 625 ms 26972 KB Output is correct
13 Correct 866 ms 48616 KB Output is correct
14 Correct 797 ms 48516 KB Output is correct
15 Correct 714 ms 44996 KB Output is correct
16 Correct 729 ms 45080 KB Output is correct
17 Correct 735 ms 44972 KB Output is correct
18 Correct 723 ms 44796 KB Output is correct
19 Correct 740 ms 44996 KB Output is correct
20 Correct 375 ms 37008 KB Output is correct
21 Correct 46 ms 22928 KB Output is correct
22 Correct 476 ms 42248 KB Output is correct
23 Correct 458 ms 41836 KB Output is correct
24 Correct 550 ms 42308 KB Output is correct
25 Correct 430 ms 40900 KB Output is correct
26 Correct 597 ms 44532 KB Output is correct
27 Correct 887 ms 50008 KB Output is correct
28 Correct 692 ms 46564 KB Output is correct
29 Correct 1000 ms 49604 KB Output is correct
30 Correct 315 ms 35700 KB Output is correct
31 Correct 917 ms 49052 KB Output is correct
32 Correct 479 ms 40516 KB Output is correct
33 Correct 477 ms 42564 KB Output is correct
34 Correct 576 ms 43832 KB Output is correct
35 Correct 544 ms 43216 KB Output is correct
36 Correct 464 ms 40900 KB Output is correct
37 Correct 446 ms 37680 KB Output is correct
38 Correct 519 ms 42560 KB Output is correct
39 Correct 705 ms 44904 KB Output is correct
40 Correct 494 ms 41412 KB Output is correct
41 Correct 456 ms 39492 KB Output is correct

Subtask #5
0 / 43.0

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