oj.uz

Submission #431894

# Submission time Handle Problem Language Result Execution time Memory
431894 2021-06-17T16:50:12 Z Pichon5 Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 453220 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());
    for(int i=0;i<l.size();i++){
        ll ind=A[i].S;
        ll equis;
        ll ant=-1;
        for(int j=l[ind];j<=r[ind];j++){
            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:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<l.size();i++){
      |                 ~^~~~~~~~~
walk.cpp:48:16: warning: 'entrada' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |     dis[entrada]=0ll;
      |                ^
walk.cpp:63:18: warning: 'salida' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |     if(dis[salida]==INF)return -1;
      |                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 63088 KB Output is correct
2 Correct 36 ms 63188 KB Output is correct
3 Correct 38 ms 63112 KB Output is correct
4 Correct 35 ms 63120 KB Output is correct
5 Correct 37 ms 63120 KB Output is correct
6 Correct 34 ms 63112 KB Output is correct
7 Correct 34 ms 63180 KB Output is correct
8 Correct 35 ms 63108 KB Output is correct
9 Correct 33 ms 63140 KB Output is correct
10 Correct 37 ms 63220 KB Output is correct
11 Correct 34 ms 63128 KB Output is correct
12 Correct 35 ms 63180 KB Output is correct
13 Correct 35 ms 63128 KB Output is correct
14 Correct 39 ms 63068 KB Output is correct
15 Correct 38 ms 63076 KB Output is correct
16 Correct 34 ms 63132 KB Output is correct
17 Correct 38 ms 63216 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 63180 KB Output is correct
2 Correct 34 ms 63076 KB Output is correct
3 Correct 457 ms 122452 KB Output is correct
4 Correct 535 ms 126812 KB Output is correct
5 Correct 335 ms 118344 KB Output is correct
6 Correct 1153 ms 112076 KB Output is correct
7 Correct 298 ms 118484 KB Output is correct
8 Correct 557 ms 138340 KB Output is correct
9 Correct 333 ms 118028 KB Output is correct
10 Correct 680 ms 151072 KB Output is correct
11 Correct 334 ms 96300 KB Output is correct
12 Correct 286 ms 85896 KB Output is correct
13 Correct 628 ms 139980 KB Output is correct
14 Execution timed out 4050 ms 84456 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 73960 KB Output is correct
2 Runtime error 740 ms 453220 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 112 ms 73960 KB Output is correct
2 Runtime error 740 ms 453220 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 40 ms 63088 KB Output is correct
2 Correct 36 ms 63188 KB Output is correct
3 Correct 38 ms 63112 KB Output is correct
4 Correct 35 ms 63120 KB Output is correct
5 Correct 37 ms 63120 KB Output is correct
6 Correct 34 ms 63112 KB Output is correct
7 Correct 34 ms 63180 KB Output is correct
8 Correct 35 ms 63108 KB Output is correct
9 Correct 33 ms 63140 KB Output is correct
10 Correct 37 ms 63220 KB Output is correct
11 Correct 34 ms 63128 KB Output is correct
12 Correct 35 ms 63180 KB Output is correct
13 Correct 35 ms 63128 KB Output is correct
14 Correct 39 ms 63068 KB Output is correct
15 Correct 38 ms 63076 KB Output is correct
16 Correct 34 ms 63132 KB Output is correct
17 Correct 38 ms 63216 KB Output is correct
18 Correct 33 ms 63180 KB Output is correct
19 Correct 34 ms 63076 KB Output is correct
20 Correct 457 ms 122452 KB Output is correct
21 Correct 535 ms 126812 KB Output is correct
22 Correct 335 ms 118344 KB Output is correct
23 Correct 1153 ms 112076 KB Output is correct
24 Correct 298 ms 118484 KB Output is correct
25 Correct 557 ms 138340 KB Output is correct
26 Correct 333 ms 118028 KB Output is correct
27 Correct 680 ms 151072 KB Output is correct
28 Correct 334 ms 96300 KB Output is correct
29 Correct 286 ms 85896 KB Output is correct
30 Correct 628 ms 139980 KB Output is correct
31 Execution timed out 4050 ms 84456 KB Time limit exceeded
32 Halted 0 ms 0 KB -