oj.uz

Submission #1036592

# Submission time Handle Problem Language Result Execution time Memory
1036592 2024-07-27T14:35:22 Z Itamar Sky Walking (IOI19_walk) C++14
0 / 100
 3486 ms 331092 KB 
using namespace std;
#include<bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define pll pair<ll,ll>
#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();
    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<pi,vector<pi>> fr;
    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();
        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];
            bel = p;
            it++;
        }
        for(pi hei : rem[i])poi.erase(poi.find(hei));
    }
    map<pi,ll> dp;
    for(auto[u,v] : fr){
        dp[u]=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));
            if(w<dp[f])se.insert({w,f});
            dp[f] = min(dp[f],w);
        }
    }
    if(dp[{x[g],0}]==1e18)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:39:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for(auto[u,v] : fr){
      |             ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Correct 4 ms 9652 KB Output is correct
3 Incorrect 4 ms 9820 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9844 KB Output is correct
3 Correct 2545 ms 223148 KB Output is correct
4 Correct 1782 ms 246868 KB Output is correct
5 Correct 651 ms 171856 KB Output is correct
6 Correct 583 ms 154196 KB Output is correct
7 Correct 623 ms 171772 KB Output is correct
8 Correct 3486 ms 279588 KB Output is correct
9 Correct 823 ms 177980 KB Output is correct
10 Correct 2823 ms 331092 KB Output is correct
11 Correct 961 ms 132224 KB Output is correct
12 Correct 494 ms 105044 KB Output is correct
13 Correct 2200 ms 294956 KB Output is correct
14 Correct 307 ms 81492 KB Output is correct
15 Incorrect 439 ms 91732 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 32016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 32016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Correct 4 ms 9652 KB Output is correct
3 Incorrect 4 ms 9820 KB Output isn't correct
4 Halted 0 ms 0 KB -