oj.uz

Submission #823837

# Submission time Handle Problem Language Result Execution time Memory
823837 2023-08-13T08:22:00 Z vjudge1 Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 1048576 KB 
#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 ;
//}

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: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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33860 KB Output is correct
2 Correct 17 ms 33960 KB Output is correct
3 Correct 18 ms 33964 KB Output is correct
4 Correct 18 ms 33972 KB Output is correct
5 Correct 20 ms 34516 KB Output is correct
6 Correct 20 ms 34388 KB Output is correct
7 Correct 19 ms 34416 KB Output is correct
8 Correct 20 ms 34380 KB Output is correct
9 Correct 18 ms 34004 KB Output is correct
10 Correct 22 ms 34884 KB Output is correct
11 Correct 19 ms 33908 KB Output is correct
12 Correct 18 ms 34004 KB Output is correct
13 Correct 19 ms 33876 KB Output is correct
14 Correct 20 ms 33936 KB Output is correct
15 Correct 18 ms 33872 KB Output is correct
16 Correct 18 ms 33936 KB Output is correct
17 Correct 20 ms 34932 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33868 KB Output is correct
2 Correct 18 ms 33896 KB Output is correct
3 Execution timed out 4125 ms 962976 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2407 ms 54160 KB Output is correct
2 Runtime error 2343 ms 1048576 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2407 ms 54160 KB Output is correct
2 Runtime error 2343 ms 1048576 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33860 KB Output is correct
2 Correct 17 ms 33960 KB Output is correct
3 Correct 18 ms 33964 KB Output is correct
4 Correct 18 ms 33972 KB Output is correct
5 Correct 20 ms 34516 KB Output is correct
6 Correct 20 ms 34388 KB Output is correct
7 Correct 19 ms 34416 KB Output is correct
8 Correct 20 ms 34380 KB Output is correct
9 Correct 18 ms 34004 KB Output is correct
10 Correct 22 ms 34884 KB Output is correct
11 Correct 19 ms 33908 KB Output is correct
12 Correct 18 ms 34004 KB Output is correct
13 Correct 19 ms 33876 KB Output is correct
14 Correct 20 ms 33936 KB Output is correct
15 Correct 18 ms 33872 KB Output is correct
16 Correct 18 ms 33936 KB Output is correct
17 Correct 20 ms 34932 KB Output is correct
18 Correct 18 ms 33868 KB Output is correct
19 Correct 18 ms 33896 KB Output is correct
20 Execution timed out 4125 ms 962976 KB Time limit exceeded
21 Halted 0 ms 0 KB -