oj.uz

Submission #1036602

# Submission time Handle Problem Language Result Execution time Memory
1036602 2024-07-27T14:42:12 Z Itamar Sky Walking (IOI19_walk) C++14
0 / 100
 3566 ms 331812 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));
            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 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Incorrect 4 ms 9760 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 9700 KB Output is correct
3 Correct 2595 ms 223116 KB Output is correct
4 Correct 1801 ms 247688 KB Output is correct
5 Correct 644 ms 172272 KB Output is correct
6 Correct 624 ms 154532 KB Output is correct
7 Correct 622 ms 172344 KB Output is correct
8 Correct 3566 ms 279692 KB Output is correct
9 Correct 805 ms 178548 KB Output is correct
10 Correct 2798 ms 331812 KB Output is correct
11 Correct 992 ms 132460 KB Output is correct
12 Correct 492 ms 105416 KB Output is correct
13 Correct 2138 ms 294992 KB Output is correct
14 Correct 327 ms 81768 KB Output is correct
15 Incorrect 359 ms 91604 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 43.0

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