oj.uz

Submission #431903

# Submission time Handle Problem Language Result Execution time Memory
431903 2021-06-17T17:00:19 Z Pichon5 Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 453300 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define ll long long
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
using namespace std;
const ll INF=2ll*1e18;
const int tam=2000005;
vector<pair<ll,ll> > G[tam];
pair<ll,ll> E[tam];
vector<bool>vis(tam,false);
vll dis(tam,INF);
long long min_distance(vi x,vi h,vi l, vi r,vi y,int s,int g){
    ll n=x.size();
    ll curr=0;
    ll entrada,salida;
    for(int i=0;i<n;i++){
        E[i]={curr,0};
        if(i==s)entrada=curr;
        if(i==g)salida=curr;
        curr++;
    }
    vector<pair<ll,ll> >A;//altura e indice
    for(int i=0;i<l.size();i++)A.pb({y[i],i});
    sort(A.begin(),A.end());
    set<ll>st;
    for(int i=0;i<n;i++)st.insert(i);
    for(int i=0;i<l.size();i++){
        ll ind=A[i].S;
        ll equis;
        ll ant=-1;
        for(auto it=st.lower_bound(l[ind]);it!=st.end() && *it<=r[ind];it++){
            int j=*it;
            if(h[j]<y[ind])continue;
            G[curr].pb({E[j].F,y[ind]-E[j].S});
            G[E[j].F].pb({curr,y[ind]-E[j].S});
            E[j]={curr,y[ind]};
            if(ant!=-1){
                G[curr].pb({ant,x[j]-equis});
                G[ant].pb({curr,x[j]-equis});
            }
            ant=curr;
            equis=x[j];
            curr++;
        }
    }
    priority_queue<pair<ll,ll> >q;
    dis[entrada]=0ll;
    q.push({0ll,entrada});
    while(!q.empty()){
        ll nodo=q.top().S;
        q.pop();
        if(vis[nodo])continue;
        vis[nodo]=1;
        for(auto it : G[nodo]){
            ll to=it.F,w=it.S;
            if(dis[nodo]+w<dis[to]){
                dis[to]=dis[nodo]+w;
                q.push({-dis[to],to});
            }
        }
    }
    if(dis[salida]==INF)return -1;
    return dis[salida];
}
/*
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
*/

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:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0;i<l.size();i++)A.pb({y[i],i});
      |                 ~^~~~~~~~~
walk.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=0;i<l.size();i++){
      |                 ~^~~~~~~~~
walk.cpp:43:37: warning: 'equis' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |                 G[ant].pb({curr,x[j]-equis});
walk.cpp:51:16: warning: 'entrada' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |     dis[entrada]=0ll;
      |                ^
walk.cpp:66:18: warning: 'salida' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |     if(dis[salida]==INF)return -1;
      |                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 63176 KB Output is correct
2 Correct 45 ms 63144 KB Output is correct
3 Correct 39 ms 63180 KB Output is correct
4 Correct 39 ms 63160 KB Output is correct
5 Correct 40 ms 63172 KB Output is correct
6 Correct 41 ms 63108 KB Output is correct
7 Correct 40 ms 63224 KB Output is correct
8 Correct 40 ms 63128 KB Output is correct
9 Correct 41 ms 63172 KB Output is correct
10 Correct 47 ms 63244 KB Output is correct
11 Correct 41 ms 63152 KB Output is correct
12 Correct 41 ms 63156 KB Output is correct
13 Correct 46 ms 63180 KB Output is correct
14 Correct 43 ms 63156 KB Output is correct
15 Correct 41 ms 63152 KB Output is correct
16 Correct 40 ms 63120 KB Output is correct
17 Correct 41 ms 63228 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 63108 KB Output is correct
2 Correct 39 ms 63044 KB Output is correct
3 Correct 512 ms 122888 KB Output is correct
4 Correct 711 ms 131528 KB Output is correct
5 Correct 541 ms 123080 KB Output is correct
6 Correct 3686 ms 116708 KB Output is correct
7 Correct 433 ms 123200 KB Output is correct
8 Correct 594 ms 138676 KB Output is correct
9 Correct 474 ms 121744 KB Output is correct
10 Correct 791 ms 155608 KB Output is correct
11 Correct 416 ms 98144 KB Output is correct
12 Correct 388 ms 90636 KB Output is correct
13 Correct 726 ms 144692 KB Output is correct
14 Execution timed out 4078 ms 84892 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 74420 KB Output is correct
2 Runtime error 631 ms 453300 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 123 ms 74420 KB Output is correct
2 Runtime error 631 ms 453300 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 45 ms 63176 KB Output is correct
2 Correct 45 ms 63144 KB Output is correct
3 Correct 39 ms 63180 KB Output is correct
4 Correct 39 ms 63160 KB Output is correct
5 Correct 40 ms 63172 KB Output is correct
6 Correct 41 ms 63108 KB Output is correct
7 Correct 40 ms 63224 KB Output is correct
8 Correct 40 ms 63128 KB Output is correct
9 Correct 41 ms 63172 KB Output is correct
10 Correct 47 ms 63244 KB Output is correct
11 Correct 41 ms 63152 KB Output is correct
12 Correct 41 ms 63156 KB Output is correct
13 Correct 46 ms 63180 KB Output is correct
14 Correct 43 ms 63156 KB Output is correct
15 Correct 41 ms 63152 KB Output is correct
16 Correct 40 ms 63120 KB Output is correct
17 Correct 41 ms 63228 KB Output is correct
18 Correct 40 ms 63108 KB Output is correct
19 Correct 39 ms 63044 KB Output is correct
20 Correct 512 ms 122888 KB Output is correct
21 Correct 711 ms 131528 KB Output is correct
22 Correct 541 ms 123080 KB Output is correct
23 Correct 3686 ms 116708 KB Output is correct
24 Correct 433 ms 123200 KB Output is correct
25 Correct 594 ms 138676 KB Output is correct
26 Correct 474 ms 121744 KB Output is correct
27 Correct 791 ms 155608 KB Output is correct
28 Correct 416 ms 98144 KB Output is correct
29 Correct 388 ms 90636 KB Output is correct
30 Correct 726 ms 144692 KB Output is correct
31 Execution timed out 4078 ms 84892 KB Time limit exceeded
32 Halted 0 ms 0 KB -