제출 #823837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
823837		vjudge1	Sky Walking (IOI19_walk)	C++14	10 / 100	4125 ms	1048576 KiB

walk

#include<bits/stdc++.h>
#include "walk.h"
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 1e5 ;
vector<ll> all[N + 1] ;
vector<pair<ll, ll>> v[10 * N + 1] ;
ll dist[10 * N + 1] ;
ll deikstra(ll fr, ll to)
{
    for(ll i = 0 ; i < 10 * N ; i++)
        dist[i] = 1e18 ;
    set<pair<ll, ll>> s ;
    s.insert({0, fr}) ;
    dist[fr] = 0 ;
    while(s.size())
    {
        ll city = (*s.begin()).se, ds = (*s.begin()).fi ;
        s.erase(s.begin()) ;
        if(ds > dist[city])
            continue ;
        for(auto i : v[city])
        {
            if(dist[i.fi] <= ds + i.se)
                continue ;
            dist[i.fi] = ds + i.se ;
            s.insert({dist[i.fi], i.fi}) ;
        }
    }
    return dist[to] ;
}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
    ll n = x.size(), m = l.size(), ans = 0 ;
    if(x.size() <= 50 && l.size() <= 50)
    {
        ll cnt = 0 ;
        map<pair<ll, ll>, ll> mp ;
        set<pair<ll, ll>> st ;
        st.insert({0, s}) ;
        st.insert({0, g}) ;
        for(ll j = 0 ; j < m ; j++)
        {
            for(ll q = l[j] ; q <= r[j] ; q++)
                if(h[q] >= y[j])
                    st.insert({y[j], q}) ;
        }
        for(auto i : st)
        {
            all[i.se].push_back(i.fi) ;
            cnt++ ;
            mp[i] = cnt ;
        }
        for(ll i = 0 ; i < n ; i++)
            for(ll j = 0 ; j < all[i].size() ; j++)
                for(ll q = j + 1 ; q < all[i].size() ; q++)
                {
                    ll to = mp[{all[i][j], i}], fr = mp[{all[i][q], i}] ;
                    if(to == fr)
                        continue ;
                    v[fr].push_back({to, abs(all[i][j] - all[i][q])}) ;
                    v[to].push_back({fr, abs(all[i][j] - all[i][q])}) ;
                }
        for(ll i = 0 ; i < n ; i++)
            for(ll j = 0 ; j < m ; j++)
            {
                if(y[j] > h[i] || i < l[j] || i > r[j])
                    continue ;
                ll fr = mp[{y[j], i}] ;
                for(ll q = i + 1 ; q <= r[j] ; q++)
                    if(h[q] >= y[j])
                    {
                        ll to = mp[{y[j], q}] ;
                        v[fr].push_back({to, abs(x[i] - x[q])}) ;
                        v[to].push_back({fr, abs(x[i] - x[q])}) ;
                    }
            }
        ans = deikstra(mp[{0, s}], mp[{0, g}]) ;
        if(ans == 1e18)
            ans = -1 ;
        return ans ;
    }
}
//signed main()
//{
//    ios_base::sync_with_stdio( 0 ) ;
//    cin.tie( 0 ) ;
//    cout.tie( 0 ) ;
//    int n, m, s, g ;
//    cin >> n >> m ;
//    vector<int> x(n), h(n), l(m), r(m), y(m) ;
//    for(int i = 0 ; i < n ; i++)
//        cin >> x[i] >> h[i] ;
//    for(int i = 0 ; i < m ; i++)
//        cin >> l[i] >> r[i] >> y[i] ;
//    cin >> s >> g ;
//    cout << min_distance(x, h, l, r, y, s, g) ;
//    return 0 ;
//}

컴파일 시 표준 에러 (stderr) 메시지

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:57:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for(ll j = 0 ; j < all[i].size() ; j++)
      |                            ~~^~~~~~~~~~~~~~~
walk.cpp:58:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |                 for(ll q = j + 1 ; q < all[i].size() ; q++)
      |                                    ~~^~~~~~~~~~~~~~~
walk.cpp:85:1: warning: control reaches end of non-void function [-Wreturn-type]
   85 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43