oj.uz

Submission #1050952

# Submission time Handle Problem Language Result Execution time Memory
1050952 2024-08-09T17:15:17 Z Itamar Sky Walking (IOI19_walk) C++14
24 / 100
 3928 ms 1048576 KB 
using namespace std;
#include<vector>
#include<map>
#include<set>
#define ll long long
#define vll vector<ll>
#define pll pair<ll,ll>
#include <cmath>
#define pi pair<ll,ll>
#define vi vector<int>
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) {
	int n = x.size(), m = l.size();
    map<pi,vector<pi>> fr;
    multiset<pi> poi;
    vector<vector<pi>> ins(2e5+2);
    vector<vector<pi>> rem(2e5+2);
    for(int i = 0; i < m; i++){
        ins[l[i]].push_back({y[i],i});
        rem[r[i]].push_back({y[i],i});
    }
    map<int,int> prev;
    for(int i = 0; i < n; i++){
        for(pi hei : ins[i])poi.insert(hei);
        pi bel = {x[i],0};
        auto it = poi.begin();
        vi up;
        while(it!=poi.end() && (*it).first <= h[i]){
            int cur = (*it).first;
            pi p = {x[i],cur};
            fr[p].push_back(bel);
            fr[bel].push_back(p);
            if(l[(*it).second]!=i){
                fr[p].push_back({prev[cur],cur});
                fr[{prev[cur],cur}].push_back(p);
            }
            //prev[cur]=x[i];
            up.push_back(cur);
            bel = p;
            it++;
        }
        for(int k : up)prev[k]=x[i];
        for(pi hei : rem[i])poi.erase(poi.find(hei));
    }
    map<pi,ll> dp;
    for(auto[a,b] : fr)dp[a]=1e18;
    dp[{x[g],0}]=1e18;
    dp[{x[s],0}]=0;
    set<pair<ll,pi>> se;
    map<pi,bool> vis;
    se.insert({0,{x[s],0}});
    while(!se.empty()){
        pair<ll,pi> p = *se.begin();
        pi q = p.second;
        se.erase(se.begin());
        if(vis[q])continue;
        vis[q]=1;
        for(pi f : fr[q]){
            if(vis[f])continue;
            ll w = dp[q] + (abs(f.first-q.first)+abs(f.second-q.second));
            se.insert({w,f});
            dp[f] = min(dp[f],w);
        }
    }
    if(dp[{x[g],0}]==0 || dp[{x[g],0}]>=1e16)return -1;
    return dp[{x[g],0}];
}

Compilation message

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:45:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for(auto[a,b] : fr)dp[a]=1e18;
      |             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9788 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 9816 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 6 ms 10072 KB Output is correct
11 Correct 3 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9792 KB Output is correct
17 Correct 3 ms 9820 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2307 ms 221016 KB Output is correct
4 Correct 1572 ms 243612 KB Output is correct
5 Correct 581 ms 168788 KB Output is correct
6 Correct 541 ms 151124 KB Output is correct
7 Correct 559 ms 168784 KB Output is correct
8 Correct 3276 ms 277584 KB Output is correct
9 Correct 753 ms 174728 KB Output is correct
10 Correct 2303 ms 327776 KB Output is correct
11 Correct 812 ms 129360 KB Output is correct
12 Correct 408 ms 101200 KB Output is correct
13 Correct 1926 ms 290984 KB Output is correct
14 Correct 265 ms 77904 KB Output is correct
15 Correct 410 ms 97632 KB Output is correct
16 Correct 416 ms 100556 KB Output is correct
17 Correct 417 ms 97420 KB Output is correct
18 Correct 462 ms 91320 KB Output is correct
19 Correct 19 ms 14164 KB Output is correct
20 Correct 220 ms 54868 KB Output is correct
21 Correct 354 ms 92992 KB Output is correct
22 Correct 394 ms 99796 KB Output is correct
23 Correct 697 ms 116676 KB Output is correct
24 Correct 399 ms 99276 KB Output is correct
25 Correct 362 ms 96336 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 35700 KB Output is correct
2 Runtime error 3928 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 35700 KB Output is correct
2 Runtime error 3928 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9788 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 9816 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 6 ms 10072 KB Output is correct
11 Correct 3 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9792 KB Output is correct
17 Correct 3 ms 9820 KB Output is correct
18 Correct 2 ms 9816 KB Output is correct
19 Correct 2 ms 9820 KB Output is correct
20 Correct 2307 ms 221016 KB Output is correct
21 Correct 1572 ms 243612 KB Output is correct
22 Correct 581 ms 168788 KB Output is correct
23 Correct 541 ms 151124 KB Output is correct
24 Correct 559 ms 168784 KB Output is correct
25 Correct 3276 ms 277584 KB Output is correct
26 Correct 753 ms 174728 KB Output is correct
27 Correct 2303 ms 327776 KB Output is correct
28 Correct 812 ms 129360 KB Output is correct
29 Correct 408 ms 101200 KB Output is correct
30 Correct 1926 ms 290984 KB Output is correct
31 Correct 265 ms 77904 KB Output is correct
32 Correct 410 ms 97632 KB Output is correct
33 Correct 416 ms 100556 KB Output is correct
34 Correct 417 ms 97420 KB Output is correct
35 Correct 462 ms 91320 KB Output is correct
36 Correct 19 ms 14164 KB Output is correct
37 Correct 220 ms 54868 KB Output is correct
38 Correct 354 ms 92992 KB Output is correct
39 Correct 394 ms 99796 KB Output is correct
40 Correct 697 ms 116676 KB Output is correct
41 Correct 399 ms 99276 KB Output is correct
42 Correct 362 ms 96336 KB Output is correct
43 Correct 109 ms 35700 KB Output is correct
44 Runtime error 3928 ms 1048576 KB Execution killed with signal 9
45 Halted 0 ms 0 KB -