Submission #297605

#	Time	Username	Problem	Language	Result	Execution time	Memory
297605		evpipis	Sky Walking (IOI19_walk)	C++14	24 / 100	1422 ms	242424 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, int> pli;

const int len = 1e5+5;
const ll inf = 1e18;
int n, m, st, en, pos[len], hei[len];

struct edge{
    int l, r, y;

    edge(int le = 0, int ri = 0, int yi = 0){
        l = le;
        r = ri;
        y = yi;
    }

    bool operator < (const edge &other){
        if (y < other.y) return true;
        if (y > other.y) return false;
        return (l < other.l);
    }
};

vector<edge> fin;

struct{
    vector<ii> las[len], adj[10*len];
    ll dis[10*len];

    ll solve(){
        int nd = 0;
        las[st].pb(mp(++nd, 0));
        las[en].pb(mp(++nd, 0));

        vector<ii> build;
        for (int i = 0; i < n; i++)
            build.pb(mp(hei[i], i));
        sort(build.begin(), build.end());

        set<int> mys;
        for (int i = 0; i < n; i++)
            mys.insert(i);

        int po = 0;
        for (auto e: fin){
            //printf("e: l = %d, r = %d, y = %d\n", e.l, e.r, e.y);
            while (po < n && build[po].fi < e.y)
                mys.erase(build[po++].se);

            int a = e.l, b = e.r, y = e.y;
            vector<int> temp;
            while (a != b){
                temp.pb(a);
                a = *mys.lower_bound(a+1);
            }
            temp.pb(b);

            //printf("temp:");
            //for (auto it: temp)
              //  printf(" %d", it);
            //printf("\n");

            for (int j = 0; j < temp.size(); j++){
                int b = temp[j], cur = ++nd;
                if (!las[b].empty()){
                    adj[cur].pb(mp(las[b].back().fi, y-las[b].back().se));
                    adj[las[b].back().fi].pb(mp(cur, y-las[b].back().se));
                }

                las[b].pb(mp(cur, y));

                if (j > 0){
                    adj[cur].pb(mp(nd-1, pos[b]-pos[temp[j-1]]));
                    adj[nd-1].pb(mp(cur, pos[b]-pos[temp[j-1]]));
                }
            }
        }

        //printf("graph is ready\n");

        /// shortest path
        for (int i = 1; i <= nd; i++)
            dis[i] = inf;

        priority_queue<pli, vector<pli>, greater<pli> > pq;
        pq.push(mp(0, 1));
        while (!pq.empty()){
            ll d = pq.top().fi;
            int u = pq.top().se;
            pq.pop();

            if (dis[u] != inf)
                continue;
            dis[u] = d;

            for (auto v: adj[u])
                pq.push(mp(d+v.se, v.fi));
        }

        if (dis[2] == inf) return -1;
        else return dis[2];
    }
} sub2;

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int G) {
    // take input
    n = X.size();
    for (int i = 0; i < n; i++)
        pos[i] = X[i], hei[i] = H[i];

    m = L.size();
    vector<edge> temp;
    for (int i = 0; i < m; i++)
        temp.pb(edge(L[i], R[i], Y[i]));
    sort(temp.begin(), temp.end());

    //printf("temp =\n");
    //for (auto e: temp)
      //  printf("e: l = %d, r = %d, y = %d\n", e.l, e.r, e.y);

    for (int i = 0; i < m; i++){
        int j = i;
        while (j+1 < m && temp[j+1].y == temp[j].y && temp[j+1].l == temp[j].r)
            j++;

        fin.pb(edge(temp[i].l, temp[j].r, temp[i].y));
    }
    m = fin.size();

    st = S, en = G;

    //printf("after read\n");
    //printf("n = %d, m = %d, st = %d, en = %d\n", n, m, st, en);

    return sub2.solve();
	return 1;
}

Compilation message (stderr)

walk.cpp: In member function 'll<unnamed struct>::solve()':
walk.cpp:72:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for (int j = 0; j < temp.size(); j++){
      |                             ~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43