oj.uz

Submission #431908

# Submission time Handle Problem Language Result Execution time Memory
431908 2021-06-17T17:02:33 Z Pichon5 Sky Walking (IOI19_walk) C++17
24 / 100
 860 ms 453276 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;
        vll AUX;
        for(auto it=st.lower_bound(l[ind]);it!=st.end() && *it<=r[ind];it++){
            ll j=*it;
            if(h[j]<y[ind]){
                AUX.pb(j);
                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++;
        }
        for(int k=0;k<AUX.size();k++){
            auto I=st.find(AUX[k]);
            st.erase(I);
        }
    }
    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:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int k=0;k<AUX.size();k++){
      |                     ~^~~~~~~~~~~
walk.cpp:47:37: warning: 'equis' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |                 G[ant].pb({curr,x[j]-equis});
walk.cpp:59:16: warning: 'entrada' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     dis[entrada]=0ll;
      |                ^
walk.cpp:74:18: warning: 'salida' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |     if(dis[salida]==INF)return -1;
      |                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 63152 KB Output is correct
2 Correct 38 ms 63100 KB Output is correct
3 Correct 38 ms 63136 KB Output is correct
4 Correct 38 ms 63096 KB Output is correct
5 Correct 37 ms 63104 KB Output is correct
6 Correct 35 ms 63128 KB Output is correct
7 Correct 39 ms 63176 KB Output is correct
8 Correct 34 ms 63112 KB Output is correct
9 Correct 34 ms 63092 KB Output is correct
10 Correct 39 ms 63172 KB Output is correct
11 Correct 42 ms 63172 KB Output is correct
12 Correct 37 ms 63132 KB Output is correct
13 Correct 35 ms 63100 KB Output is correct
14 Correct 45 ms 63096 KB Output is correct
15 Correct 39 ms 63176 KB Output is correct
16 Correct 33 ms 63092 KB Output is correct
17 Correct 34 ms 63188 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 63180 KB Output is correct
2 Correct 39 ms 63088 KB Output is correct
3 Correct 530 ms 122688 KB Output is correct
4 Correct 728 ms 130200 KB Output is correct
5 Correct 395 ms 118540 KB Output is correct
6 Correct 400 ms 112412 KB Output is correct
7 Correct 391 ms 118832 KB Output is correct
8 Correct 593 ms 138376 KB Output is correct
9 Correct 513 ms 119836 KB Output is correct
10 Correct 860 ms 152896 KB Output is correct
11 Correct 407 ms 97212 KB Output is correct
12 Correct 382 ms 90456 KB Output is correct
13 Correct 807 ms 143356 KB Output is correct
14 Correct 259 ms 85008 KB Output is correct
15 Correct 306 ms 86812 KB Output is correct
16 Correct 332 ms 88320 KB Output is correct
17 Correct 323 ms 87228 KB Output is correct
18 Correct 201 ms 89016 KB Output is correct
19 Correct 43 ms 64308 KB Output is correct
20 Correct 118 ms 74076 KB Output is correct
21 Correct 307 ms 88736 KB Output is correct
22 Correct 404 ms 91488 KB Output is correct
23 Correct 286 ms 92872 KB Output is correct
24 Correct 327 ms 89136 KB Output is correct
25 Correct 376 ms 88872 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 74372 KB Output is correct
2 Runtime error 644 ms 453276 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 129 ms 74372 KB Output is correct
2 Runtime error 644 ms 453276 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 37 ms 63152 KB Output is correct
2 Correct 38 ms 63100 KB Output is correct
3 Correct 38 ms 63136 KB Output is correct
4 Correct 38 ms 63096 KB Output is correct
5 Correct 37 ms 63104 KB Output is correct
6 Correct 35 ms 63128 KB Output is correct
7 Correct 39 ms 63176 KB Output is correct
8 Correct 34 ms 63112 KB Output is correct
9 Correct 34 ms 63092 KB Output is correct
10 Correct 39 ms 63172 KB Output is correct
11 Correct 42 ms 63172 KB Output is correct
12 Correct 37 ms 63132 KB Output is correct
13 Correct 35 ms 63100 KB Output is correct
14 Correct 45 ms 63096 KB Output is correct
15 Correct 39 ms 63176 KB Output is correct
16 Correct 33 ms 63092 KB Output is correct
17 Correct 34 ms 63188 KB Output is correct
18 Correct 37 ms 63180 KB Output is correct
19 Correct 39 ms 63088 KB Output is correct
20 Correct 530 ms 122688 KB Output is correct
21 Correct 728 ms 130200 KB Output is correct
22 Correct 395 ms 118540 KB Output is correct
23 Correct 400 ms 112412 KB Output is correct
24 Correct 391 ms 118832 KB Output is correct
25 Correct 593 ms 138376 KB Output is correct
26 Correct 513 ms 119836 KB Output is correct
27 Correct 860 ms 152896 KB Output is correct
28 Correct 407 ms 97212 KB Output is correct
29 Correct 382 ms 90456 KB Output is correct
30 Correct 807 ms 143356 KB Output is correct
31 Correct 259 ms 85008 KB Output is correct
32 Correct 306 ms 86812 KB Output is correct
33 Correct 332 ms 88320 KB Output is correct
34 Correct 323 ms 87228 KB Output is correct
35 Correct 201 ms 89016 KB Output is correct
36 Correct 43 ms 64308 KB Output is correct
37 Correct 118 ms 74076 KB Output is correct
38 Correct 307 ms 88736 KB Output is correct
39 Correct 404 ms 91488 KB Output is correct
40 Correct 286 ms 92872 KB Output is correct
41 Correct 327 ms 89136 KB Output is correct
42 Correct 376 ms 88872 KB Output is correct
43 Correct 129 ms 74372 KB Output is correct
44 Runtime error 644 ms 453276 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -