oj.uz

Submission #431897

# Submission time Handle Problem Language Result Execution time Memory
431897 2021-06-17T16:55:59 Z Pichon5 Sky Walking (IOI19_walk) C++17
0 / 100
 638 ms 453516 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<int>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;
        auto it=st.lower_bound(l[ind]);
        vi aux;
        for(it;(*it)<=r[ind] && it!=st.end();it++){
            int 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 j=0;j<aux.size();j++){
            st.erase(aux[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:37:13: warning: statement has no effect [-Wunused-value]
   37 |         for(it;(*it)<=r[ind] && it!=st.end();it++){
      |             ^~
walk.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j=0;j<aux.size();j++){
      |                     ~^~~~~~~~~~~
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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 63180 KB Output is correct
2 Correct 41 ms 63180 KB Output is correct
3 Correct 37 ms 63128 KB Output is correct
4 Correct 37 ms 63132 KB Output is correct
5 Correct 37 ms 63168 KB Output is correct
6 Correct 36 ms 63208 KB Output is correct
7 Correct 37 ms 63180 KB Output is correct
8 Correct 36 ms 63172 KB Output is correct
9 Correct 36 ms 63104 KB Output is correct
10 Correct 36 ms 63204 KB Output is correct
11 Correct 38 ms 63212 KB Output is correct
12 Correct 38 ms 63188 KB Output is correct
13 Correct 39 ms 63096 KB Output is correct
14 Correct 37 ms 63180 KB Output is correct
15 Correct 36 ms 63080 KB Output is correct
16 Correct 37 ms 63180 KB Output is correct
17 Incorrect 37 ms 63180 KB Output isn't correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 63092 KB Output is correct
2 Correct 36 ms 63128 KB Output is correct
3 Runtime error 167 ms 145920 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 74344 KB Output is correct
2 Runtime error 638 ms 453516 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 117 ms 74344 KB Output is correct
2 Runtime error 638 ms 453516 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 36 ms 63180 KB Output is correct
2 Correct 41 ms 63180 KB Output is correct
3 Correct 37 ms 63128 KB Output is correct
4 Correct 37 ms 63132 KB Output is correct
5 Correct 37 ms 63168 KB Output is correct
6 Correct 36 ms 63208 KB Output is correct
7 Correct 37 ms 63180 KB Output is correct
8 Correct 36 ms 63172 KB Output is correct
9 Correct 36 ms 63104 KB Output is correct
10 Correct 36 ms 63204 KB Output is correct
11 Correct 38 ms 63212 KB Output is correct
12 Correct 38 ms 63188 KB Output is correct
13 Correct 39 ms 63096 KB Output is correct
14 Correct 37 ms 63180 KB Output is correct
15 Correct 36 ms 63080 KB Output is correct
16 Correct 37 ms 63180 KB Output is correct
17 Incorrect 37 ms 63180 KB Output isn't correct