oj.uz

Submission #552229

# Submission time Handle Problem Language Result Execution time Memory
552229 2022-04-22T20:04:23 Z PiejanVDC Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 566084 KB 
#include<bits/stdc++.h>
using namespace std;

#include "walk.h"

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
    const long long n = (long long)x.size();
    const long long m = (long long)l.size();

    vector<set<long long>>v(n);

    v[g].insert(0);

    set<pair<long long,pair<long long,long long>>>connected;

    for(long long i = 0 ; i < m ; i++) {
        if(m == 0) break;
        for(long long ii = l[i] ; ii <= r[i] ; ii++) {
            if(ii < r[i])
                connected.insert({y[i], {ii, ii+1}});
            v[ii].insert(y[i]);
        }
    }

    map<pair<long long,long long>,long long>dist;

    priority_queue<pair<long long,pair<long long,long long>>>pq;
    pq.push({0,{s,0}});

    while(!pq.empty()) {
        auto node = pq.top();
        pq.pop();
        auto [i,y] = node.second;
        if(i > 0 && v[i-1].count(y) && connected.count({y, {i-1,i}})) {
            if((!dist.count({i-1,y}) || dist[{i,y}] + x[i] - x[i-1] < dist[{i-1,y}])) {
                dist[{i-1,y}] = dist[{i,y}] + x[i] - x[i-1];
                pq.push({-dist[{i-1,y}], {i-1, y}});
            }
        }
        if(i < n-1 && v[i+1].count(y) && connected.count({y, {i,i+1}})) {
            if((!dist.count({i+1,y}) || dist[{i,y}] + x[i+1] - x[i] < dist[{i+1,y}])) {
                dist[{i+1,y}] = dist[{i,y}] + x[i+1] - x[i];
                pq.push({-dist[{i+1,y}], {i+1, y}});
            }
        }
        for(auto it = v[i].begin() ; it != v[i].end() ; it++) {
            long long yy = *it;
            if(yy > h[i] || y > h[i])
                break;
            if(!dist[{i,yy}] || dist[{i,y}] + abs(y - yy) < dist[{i,yy}]) {
                dist[{i,yy}] = dist[{i,y}] + abs(y - yy);
                pq.push({-dist[{i,yy}], {i, yy}});
            }
        }
    }
    if(!dist[{g,0}])
        return -1;
    return dist[{g,0}];
}
/*
//#include "walk.h"
#include <cstdio>
#include <cassert>

using namespace std;

int main() {
	int n, m;
	assert(2 == scanf("%d%d", &n, &m));
	vector<int> x(n), h(n);
	for (int i = 0; i < n; i++)
		assert(2 == scanf("%d%d", &x[i], &h[i]));
	vector<int> l(m), r(m), y(m);
	for (int i = 0; i < m; i++)
		assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
	int s, g;
	assert(2 == scanf("%d%d", &s, &g));
	fclose(stdin);

	long long result = min_distance(x, h, l, r, y, s, g);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}
*/

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 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 3 ms 436 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 432 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 6 ms 468 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 0 ms 212 KB Output is correct
3 Execution timed out 4085 ms 94128 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 12348 KB Output is correct
2 Execution timed out 4083 ms 566084 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 12348 KB Output is correct
2 Execution timed out 4083 ms 566084 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 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 3 ms 436 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 432 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 6 ms 468 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Execution timed out 4085 ms 94128 KB Time limit exceeded
21 Halted 0 ms 0 KB -