oj.uz

Submission #610913

# Submission time Handle Problem Language Result Execution time Memory
610913 2022-07-28T18:14:21 Z fvogel499 Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 759608 KB 
#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];
    if (res >= inf) res = -1;
    return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 444 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 1 ms 444 KB Output is correct
8 Correct 1 ms 440 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 2 ms 568 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2 ms 568 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1915 ms 231648 KB Output is correct
4 Incorrect 1602 ms 234804 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 31080 KB Output is correct
2 Execution timed out 4043 ms 759608 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 31080 KB Output is correct
2 Execution timed out 4043 ms 759608 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 444 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 1 ms 444 KB Output is correct
8 Correct 1 ms 440 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 2 ms 568 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2 ms 568 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1915 ms 231648 KB Output is correct
21 Incorrect 1602 ms 234804 KB Output isn't correct
22 Halted 0 ms 0 KB -