oj.uz

Submission #1036588

# Submission time Handle Problem Language Result Execution time Memory
1036588 2024-07-27T14:33:17 Z Itamar Sky Walking (IOI19_walk) C++14
0 / 100
 3605 ms 299624 KB 
using namespace std;
#include<bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define pll pair<ll,ll>
#define pi pair<int,int>
#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 9816 KB Output is correct
2 Correct 5 ms 9732 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 5 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 2831 ms 199076 KB Output is correct
4 Correct 2049 ms 225876 KB Output is correct
5 Correct 669 ms 153216 KB Output is correct
6 Correct 607 ms 138036 KB Output is correct
7 Correct 645 ms 153212 KB Output is correct
8 Correct 3605 ms 249156 KB Output is correct
9 Correct 870 ms 158800 KB Output is correct
10 Correct 3022 ms 299624 KB Output is correct
11 Correct 1027 ms 119888 KB Output is correct
12 Correct 539 ms 100640 KB Output is correct
13 Correct 2438 ms 268496 KB Output is correct
14 Correct 289 ms 76112 KB Output is correct
15 Incorrect 398 ms 85452 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 27600 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 9816 KB Output is correct
2 Correct 5 ms 9732 KB Output is correct
3 Incorrect 4 ms 9820 KB Output isn't correct
4 Halted 0 ms 0 KB -