oj.uz

Submission #1050940

# Submission time Handle Problem Language Result Execution time Memory
1050940 2024-08-09T17:04:28 Z Itamar Sky Walking (IOI19_walk) C++14
0 / 100
 3265 ms 331828 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();
    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();
        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[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:39:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for(auto[a,b] : fr)dp[a]=1e18;
      |             ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Incorrect 3 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 3 ms 9816 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 2242 ms 221104 KB Output is correct
4 Correct 1625 ms 247680 KB Output is correct
5 Correct 595 ms 172112 KB Output is correct
6 Correct 527 ms 154696 KB Output is correct
7 Correct 537 ms 172368 KB Output is correct
8 Correct 3265 ms 279532 KB Output is correct
9 Correct 714 ms 178468 KB Output is correct
10 Correct 2353 ms 331828 KB Output is correct
11 Correct 815 ms 132432 KB Output is correct
12 Correct 403 ms 105492 KB Output is correct
13 Correct 1926 ms 294996 KB Output is correct
14 Correct 278 ms 81576 KB Output is correct
15 Incorrect 300 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 60 ms 31324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 43.0

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