oj.uz

답안 #1040910

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1040910 2024-08-01T11:46:52 Z Itamar Sky Walking (IOI19_walk) C++14
0 / 100
 3158 ms 330196 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[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[u,v] : fr){
      |             ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9764 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 2315 ms 222288 KB Output is correct
4 Correct 1672 ms 246048 KB Output is correct
5 Correct 593 ms 170824 KB Output is correct
6 Correct 564 ms 153164 KB Output is correct
7 Correct 554 ms 170872 KB Output is correct
8 Correct 3158 ms 278868 KB Output is correct
9 Correct 734 ms 176800 KB Output is correct
10 Correct 2375 ms 330196 KB Output is correct
11 Correct 843 ms 131300 KB Output is correct
12 Correct 416 ms 103612 KB Output is correct
13 Correct 1962 ms 293328 KB Output is correct
14 Correct 275 ms 79956 KB Output is correct
15 Incorrect 313 ms 90192 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 31828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 31828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Incorrect 3 ms 9820 KB Output isn't correct
4 Halted 0 ms 0 KB -