Submission #297656

#	Time	Username	Problem	Language	Result	Execution time	Memory
297656		evpipis	Sky Walking (IOI19_walk)	C++14	57 / 100	1484 ms	246868 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;

struct{
    vector<ii> adj[len];
    ll dis[len];

    void add_edge(int a, int b, int c){
        adj[a].pb(mp(b, c));
        adj[b].pb(mp(a, c));
    }

    ll find_path(int st, int en){
        for (int i = 0; i < len; i++)
            dis[i] = inf;

        priority_queue<pli, vector<pli>, greater<pli> > pq;

        pq.push(mp(0, st));
        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));
        }

        return dis[en];
    }
} graph;

struct{
    struct inter{
        int l, r, y, id;

        inter(int l_, int r_, int y_, int id_){
            l = l_;
            r = r_;
            y = y_;
            id = id_;
        }

        bool operator < (const inter &other) const{
            return (mp(l, r) < mp(other.l, other.r));
        }

        void print(){
            printf("l = %d, r = %d, y = %d, id = %d\n", l, r, y, id);
        }
    };

    set<inter> mys;

    void add_node(inter cur){
        //printf("adding new nod:\n"), cur.print();

        //printf("all candidates\n");
        //for (auto can: mys)
          //  can.print();

        vector<inter> temp;

        auto it = mys.lower_bound(inter(cur.r+1, cur.r+1, 0, 0));
        while (true){
            if (it == mys.begin())
                break;

            it--;
            if ((cur.r < it->l) || (cur.l > it->r))
                break;
            temp.pb(*it);
        }

        for (auto pre: temp){
            //printf("next adj:\n");
            //pre.print();
            graph.add_edge(cur.id, pre.id, cur.y-pre.y);

            mys.erase(pre);
            if (pre.l < cur.l)
                mys.insert(inter(pre.l, cur.l-1, pre.y, pre.id));
            if (pre.r > cur.r)
                mys.insert(inter(cur.r+1, pre.r, pre.y, pre.id));
        }

        mys.insert(cur);
    }

    ll solve(){
        //printf("edges:\n");
        //for (auto e: fin)
          //  printf("l = %d, r = %d, y = %d\n", e.l, e.r, e.y);

        int nd = 0;
        add_node(inter(st, st, 0, ++nd));
        add_node(inter(en, en, 0, ++nd));

        for (auto e: fin)
            add_node(inter(e.l, e.r, e.y, ++nd));

        ll dis = graph.find_path(1, 2);
        if (dis == inf) return -1;
        return pos[en]-pos[st] + dis;
    }
} sub4;

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);

    if (st == 0 && en == n-1)
        return sub4.solve();
    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: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43