oj.uz

답안 #932260

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
932260 2024-02-23T06:40:43 Z salmon Sky Walking (IOI19_walk) C++14
24 / 100
 4000 ms 597768 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

map<int,pair<int,int>> sky[100100];
map<int,long long int> d[100100];
map<int,set<int>> uber;
set<int> sat;
vector<pair<int,int>> v;
vector<pair<int,int>> w;


priority_queue<pair<long long int, pair<int,int>>,vector<pair<long long int, pair<int,int>>>,greater<pair<long long int, pair<int,int>>>> pq;

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {

    int N = x.size();

    for(int i = 0; i < N; i++){
        l.push_back(i);
        r.push_back(i);
        y.push_back(0);

        v.push_back({h[i],i});
        sat.insert(i);
    }

    sort(v.begin(),v.end(),greater<pair<int,int>>());

    int M = l.size();

    for(int i = 0; i < M; i++){
        w.push_back({y[i],i});
    }

    sort(w.begin(),w.end());

    for(int i = 0; i < M; i++){
        while(v.back().first < w[i].first){
            sat.erase(v.back().second);
            v.pop_back();
        }

        int j = w[i].second;

        auto it = sat.lower_bound(l[j]);

        while(it != sat.end() && (*it) <= r[j]){
            int k = (*it);
            uber[y[j]].insert(*it);
            if(sky[k].find(y[j]) != sky[k].end()){
                sky[k][y[j]].first = min(sky[k][y[j]].first,l[j]);
                sky[k][y[j]].second = max(sky[k][y[j]].second,r[j]);
            }
            else{
                sky[k][y[j]] = make_pair(l[j],r[j]);
            }
            advance(it,1);
        }
    }

    pq.push({0,{s,0}});

    while(!pq.empty()){
        pair<long long int, pair<int,int>> iii = pq.top();
        pq.pop();
        pair<int,int> ii = iii.second;

        if(d[ii.first].find(ii.second) != d[ii.first].end()){
            continue;
        }

        d[ii.first][ii.second] = iii.first;

        auto it = sky[ii.first].find(ii.second);

        advance(it,1);

        if(it != sky[ii.first].end()){
            pq.push({iii.first + (it -> first) - ii.second, {ii.first, it -> first}});
        }

        advance(it,-1);

        if(it != sky[ii.first].begin()){
            advance(it,-1);
            pq.push({iii.first + ii.second - (it -> first), {ii.first, it -> first}});
        }

        auto grab = uber[ii.second].find(ii.first);

        advance(grab,1);

        if(grab != uber[ii.second].end() && (*grab) <= sky[ii.first][ii.second].second){
            pq.push({iii.first + x[(*grab)] - x[ii.first], {(*grab), ii.second}});
        }

        advance(grab,-1);

        if(grab != uber[ii.second].begin()){
            advance(grab,-1);
            if(sky[ii.first][ii.second].first <= (*grab) ){
                pq.push({iii.first + x[ii.first] - x[(*grab)], {(*grab), ii.second}});
            }
        }


    }

    if(d[g].find(0) == d[g].end()) return -1;

	return d[g][0];
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 3 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 4 ms 9924 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9840 KB Output is correct
13 Correct 3 ms 9820 KB Output is correct
14 Correct 2 ms 9644 KB Output is correct
15 Correct 3 ms 10076 KB Output is correct
16 Correct 3 ms 9828 KB Output is correct
17 Correct 3 ms 9820 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 3 ms 9816 KB Output is correct
3 Correct 1876 ms 145248 KB Output is correct
4 Correct 1147 ms 167700 KB Output is correct
5 Correct 380 ms 102568 KB Output is correct
6 Correct 349 ms 93872 KB Output is correct
7 Correct 392 ms 102860 KB Output is correct
8 Correct 2403 ms 180820 KB Output is correct
9 Correct 613 ms 110280 KB Output is correct
10 Correct 1745 ms 218612 KB Output is correct
11 Correct 656 ms 93028 KB Output is correct
12 Correct 525 ms 81576 KB Output is correct
13 Correct 1494 ms 196164 KB Output is correct
14 Correct 222 ms 59112 KB Output is correct
15 Correct 359 ms 73016 KB Output is correct
16 Correct 383 ms 71436 KB Output is correct
17 Correct 366 ms 68916 KB Output is correct
18 Correct 420 ms 75156 KB Output is correct
19 Correct 13 ms 13144 KB Output is correct
20 Correct 128 ms 43772 KB Output is correct
21 Correct 305 ms 67348 KB Output is correct
22 Correct 363 ms 70564 KB Output is correct
23 Correct 448 ms 87784 KB Output is correct
24 Correct 363 ms 71168 KB Output is correct
25 Correct 347 ms 69192 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 24176 KB Output is correct
2 Execution timed out 4073 ms 597768 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 24176 KB Output is correct
2 Execution timed out 4073 ms 597768 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 3 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 4 ms 9924 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9840 KB Output is correct
13 Correct 3 ms 9820 KB Output is correct
14 Correct 2 ms 9644 KB Output is correct
15 Correct 3 ms 10076 KB Output is correct
16 Correct 3 ms 9828 KB Output is correct
17 Correct 3 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 3 ms 9816 KB Output is correct
20 Correct 1876 ms 145248 KB Output is correct
21 Correct 1147 ms 167700 KB Output is correct
22 Correct 380 ms 102568 KB Output is correct
23 Correct 349 ms 93872 KB Output is correct
24 Correct 392 ms 102860 KB Output is correct
25 Correct 2403 ms 180820 KB Output is correct
26 Correct 613 ms 110280 KB Output is correct
27 Correct 1745 ms 218612 KB Output is correct
28 Correct 656 ms 93028 KB Output is correct
29 Correct 525 ms 81576 KB Output is correct
30 Correct 1494 ms 196164 KB Output is correct
31 Correct 222 ms 59112 KB Output is correct
32 Correct 359 ms 73016 KB Output is correct
33 Correct 383 ms 71436 KB Output is correct
34 Correct 366 ms 68916 KB Output is correct
35 Correct 420 ms 75156 KB Output is correct
36 Correct 13 ms 13144 KB Output is correct
37 Correct 128 ms 43772 KB Output is correct
38 Correct 305 ms 67348 KB Output is correct
39 Correct 363 ms 70564 KB Output is correct
40 Correct 448 ms 87784 KB Output is correct
41 Correct 363 ms 71168 KB Output is correct
42 Correct 347 ms 69192 KB Output is correct
43 Correct 94 ms 24176 KB Output is correct
44 Execution timed out 4073 ms 597768 KB Time limit exceeded
45 Halted 0 ms 0 KB -