Submission #610912

#	Time	Username	Problem	Language	Result	Execution time	Memory
610912		fvogel499	Sky Walking (IOI19_walk)	C++17	0 / 100	4078 ms	852508 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define pii pair<int, int>
#define f first
#define s second

#define vi vector<int>

#define int long long
#define size(x) (int)((x).size())

const int inf = 1e18;
const int siz = 5e6+40;

int dist [siz];

struct Compare {
    bool operator()(int a, int b) {
        return (dist[a] > dist[b]);
    }
};

int min_distance(std::vector<signed> pos, std::vector<signed> heightOf, std::vector<signed> leftP, std::vector<signed> rightP, std::vector<signed> yLevel, signed oriX, signed tarX) {
    leftP.push_back(oriX);
    rightP.push_back(oriX);
    yLevel.push_back(0);
    leftP.push_back(tarX);
    rightP.push_back(tarX);
    yLevel.push_back(0);
	const int n = size(pos);
	const int nbP = size(leftP);
    vector<pii> insAt [n];
    vector<pii> remAt [n];
    for (int i = 0; i < nbP; i++) {
        insAt[leftP[i]].push_back({yLevel[i], i});
        remAt[rightP[i]].push_back({yLevel[i], i});
    }
    vi cut [n];
    set<pii> se;
    for (int i = 0; i < n; i++) {
        for (pii j : insAt[i]) {
            se.insert(j);
        }
        for (auto j = se.begin(); j != se.end(); j = next(j)) {
            if (j->f > heightOf[i]) {
                break;
            }
            cut[i].push_back(j->s);
        }
        for (pii j : remAt[i]) {
            se.erase(j);
        }
    }
    set<pii> possNodes;
    for (int i = 0; i < n; i++) {
        for (int j : cut[i]) possNodes.insert({i, yLevel[j]});
    }
    map<pii, int> compress;
    int cnt = 0;
    for (auto i : possNodes) compress[i] = cnt++;
    vi inter [nbP];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < size(cut[i]); j++) {
            inter[cut[i][j]].push_back(i);
        }
    }
	vector<pair<pii, int>> e;
    for (int i = 0; i < n; i++) {
        vi loc;
        for (int j : cut[i]) {
            loc.push_back(yLevel[j]);
        }
        sort(loc.begin(), loc.end());
        for (int j = 0; j < size(loc)-1; j++) {
            e.push_back({{compress[{i, loc[j]}], compress[{i, loc[j+1]}]}, loc[j+1]-loc[j]});
        }
    }
    for (int i = 0; i < nbP; i++) {
        assert(size(inter[i]) >= 1);
        for (int j = 0; j < size(inter[i])-1; j++) {
            e.push_back({{compress[{inter[i][j], yLevel[i]}], compress[{inter[i][j+1], yLevel[i]}]}, pos[inter[i][j+1]]-pos[inter[i][j]]});
        }
    }
    vector<pii> graph [size(compress)];
    for (auto i : e) {
        assert(i.s >= 0);
        graph[i.f.f].push_back({i.f.s, i.s});
        graph[i.f.s].push_back({i.f.f, i.s});
    }
    priority_queue<int, vector<int>, Compare> q;
    for (int i = 0; i < size(compress); i++) dist[i] = inf;
    dist[compress[{oriX, 0}]] = 0;
    q.push(compress[{oriX, 0}]);
    bool vis [size(compress)];
    for (int i = 0; i < size(compress); i++) vis[i] = false;
    while (!q.empty()) {
        int x = q.top();
        q.pop();
        if (vis[x]) continue;
        vis[x] = true;
        for (pii e : graph[x]) {
            int nd = dist[x]+e.s;
            if (nd < dist[e.f]) {
                dist[e.f] = nd;
                q.push(e.f);
            }
        }
    }
    int tarXEncoded = compress[{tarX, 0}];
    int res = dist[tarXEncoded];
    return res;
}

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