oj.uz

Submission #472897

# Submission time Handle Problem Language Result Execution time Memory
472897 2021-09-14T13:10:53 Z dxz05 Sky Walking (IOI19_walk) C++14
0 / 100
 4000 ms 849484 KB 
#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MP make_pair

const int MAXN = 2e6 + 3e2;

void sort(vector<int> &l, vector<int> &r, vector<int> &y){
    vector<pair<int, pair<int, int>>> vec(y.size());
    for (int i = 0; i < y.size(); i++){
        vec[i] = MP(y[i], MP(l[i], r[i]));
    }
    sort(vec.begin(), vec.end());

    for (int i = 0; i < y.size(); i++){
        y[i] = vec[i].first;
        l[i] = vec[i].second.first;
        r[i] = vec[i].second.second;
    }
}

map<int, int> mp[MAXN];
int next_id = 0;
vector<pair<int, int>> points[MAXN];

int id(int i, int h){
    if (mp[i].find(h) != mp[i].end()) return mp[i][h];
    return mp[i][h] = next_id++;
}

vector<pair<int, int>> g[MAXN];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int start, int finish) {
    int n = x.size(), m = y.size();
    sort(l, r, y);

    for (int i = 0; i < n; i++){
        points[i].emplace_back(id(i, 0), 0);
    }

    for (int i = 0; i < m; i++){
        //cout << l[i] << ' ' << r[i] << ' ' << y[i] << endl;
        int last = l[i];
        for (int j = l[i]; j <= r[i]; j++){
            if (y[i] > h[j]) continue;
            int a = id(j, y[i]);
            points[j].emplace_back(a, y[i]);

            if (j > l[i]) {
                int b = id(last, y[i]);
                g[a].emplace_back(b, x[j] - x[last]);
                g[b].emplace_back(a, x[j] - x[last]);
            }

            last = j;
        }
    }

    for (int i = 0; i < n; i++){
        points[i].emplace_back(id(i, h[i]), h[i]);
//        cout << i << endl;
        for (int j = 1; j < points[i].size(); j++){
//            cout << points[i][j].first << ' ' << points[i][j].second << endl;
            int a = points[i][j - 1].first, b = points[i][j].first, w = points[i][j].second - points[i][j - 1].second;
            g[a].emplace_back(b, w);
            g[b].emplace_back(a, w);
        }
    }

    int k = next_id;
    vector<ll> d(k, 1e18);
    vector<bool> processed(k, false);
    d[start] = 0;

    priority_queue<pair<ll, int>> pq;
    pq.push(MP(0, start));

    while (!pq.empty()){
        int v = pq.top().second; pq.pop();
        if (processed[v]) continue;
        processed[v] = true;

        for (auto e : g[v]){
            int u = e.first, w = e.second;
            if (d[u] > d[v] + w){
                d[u] = d[v] + w;
                pq.push(MP(-d[u], u));
            }
        }

    }

	return d[finish];
}

Compilation message

walk.cpp: In function 'void sort(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
walk.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 0; i < y.size(); i++){
      |                     ~~^~~~~~~~~~
walk.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < y.size(); i++){
      |                     ~~^~~~~~~~~~
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:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int j = 1; j < points[i].size(); j++){
      |                         ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 188152 KB Output is correct
2 Correct 101 ms 188112 KB Output is correct
3 Correct 106 ms 188224 KB Output is correct
4 Incorrect 101 ms 188096 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 188084 KB Output is correct
2 Correct 104 ms 188232 KB Output is correct
3 Correct 1146 ms 291312 KB Output is correct
4 Correct 1046 ms 308864 KB Output is correct
5 Correct 752 ms 293212 KB Output is correct
6 Correct 1325 ms 282256 KB Output is correct
7 Incorrect 662 ms 293312 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 201304 KB Output is correct
2 Execution timed out 4160 ms 849484 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 201304 KB Output is correct
2 Execution timed out 4160 ms 849484 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 188152 KB Output is correct
2 Correct 101 ms 188112 KB Output is correct
3 Correct 106 ms 188224 KB Output is correct
4 Incorrect 101 ms 188096 KB Output isn't correct
5 Halted 0 ms 0 KB -