oj.uz

Submission #1036489

# Submission time Handle Problem Language Result Execution time Memory
1036489 2024-07-27T12:42:12 Z Abito Sky Walking (IOI19_walk) C++17
0 / 100
 2324 ms 308352 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define int long long
#define ep insert
#define elif else if
using namespace std;
const int N=1e5+5;
int n,m,a[N],b[N],L[N],R[N],c[N],dis[N][15];
vector<pair<int,int>> ad[N],er[N];
vector<int> v[N];
set<int> s[N];
bool vis[N][15];
void dijkstra(int src){
    for (int i=1;i<=n;i++) for (int j=0;j<15;j++) dis[i][j]=LLONG_MAX;
    dis[src][11]=0;
    priority_queue<vector<int>> pq;
    pq.push({0,src,11});
    while (!pq.empty()){
        int x=pq.top()[1],y=pq.top()[2];
        pq.pop();
        if (vis[x][y]) continue;
        //cout<<x<<' '<<y<<endl;
        vis[x][y]=1;
        int h;
        if (y==11) h=0;
        elif (y==12) h=b[x];
        else h=c[v[x][y]];
        for (int i=0;i<v[x].size();i++){
            if (dis[x][i]>dis[x][y]+abs(c[v[x][i]]-h)){
                dis[x][i]=dis[x][y]+abs(c[v[x][i]]-h);
                pq.push({-dis[x][i],x,i});
            }
        }
        if (dis[x][11]>dis[x][y]+h){
            dis[x][11]=dis[x][y]+h;
            pq.push({-dis[x][11],x,11});
        }
        if (dis[x][12]>dis[x][y]+b[x]-h){
            dis[x][12]=dis[x][y]+b[x]-h;
            pq.push({-dis[x][12],x,12});
        }
        if (y>10) continue;
        auto it=s[v[x][y]].upper_bound(x);
        if (it!=s[v[x][y]].end()){
            int tox=*it,toy;
            for (int i=0;i<v[tox].size();i++) if (v[tox][i]==v[x][y]) toy=i;
            if (dis[tox][toy]>dis[x][y]+abs(a[tox]-a[x])){
                dis[tox][toy]=dis[x][y]+abs(a[tox]-a[x]);
                pq.push({-dis[tox][toy],tox,toy});
            }
        }
        it=s[v[x][y]].lower_bound(x);
        if (it!=s[v[x][y]].begin()){
            int tox=*--it,toy;
            for (int i=0;i<v[tox].size();i++) if (v[tox][i]==v[x][y]) toy=i;
            if (dis[tox][toy]>dis[x][y]+abs(a[tox]-a[x])){
                dis[tox][toy]=dis[x][y]+abs(a[tox]-a[x]);
                pq.push({-dis[tox][toy],tox,toy});
            }
        }
    }
    return;
}
long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t S, int32_t g) {
    n=x.size(),m=l.size();
    for (int i=0;i<n;i++) a[i+1]=x[i],b[i+1]=h[i];
    for (int j=0;j<m;j++) L[j+1]=l[j]+1,R[j+1]=r[j]+1,c[j+1]=y[j];
    for (int j=1;j<=m;j++){
        ad[L[j]].pb({c[j],j});
        er[R[j]].pb({c[j],j});
    }
    set<pair<int,int>> ms;
    for (int i=1;i<=n;i++){
        for (auto u:ad[i]) ms.ep(u);
        for (auto u:ms){
            if (u.F<=b[i]) v[i].pb(u.S),s[u.S].ep(i);
            else break;
        }
        for (auto u:er[i]) ms.erase(u);
    }
    dijkstra(S+1);
    if (dis[g+1][11]==LLONG_MAX) return -1;
    return dis[g+1][11];
}

Compilation message

walk.cpp: In function 'void dijkstra(long long int)':
walk.cpp:31:23: 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]
   31 |         for (int i=0;i<v[x].size();i++){
      |                      ~^~~~~~~~~~~~
walk.cpp:49:27: 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]
   49 |             for (int i=0;i<v[tox].size();i++) if (v[tox][i]==v[x][y]) toy=i;
      |                          ~^~~~~~~~~~~~~~
walk.cpp:58:27: 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 (int i=0;i<v[tox].size();i++) if (v[tox][i]==v[x][y]) toy=i;
      |                          ~^~~~~~~~~~~~~~
walk.cpp:59:29: warning: 'toy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |             if (dis[tox][toy]>dis[x][y]+abs(a[tox]-a[x])){
      |                 ~~~~~~~~~~~~^
walk.cpp:50:29: warning: 'toy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |             if (dis[tox][toy]>dis[x][y]+abs(a[tox]-a[x])){
      |                 ~~~~~~~~~~~~^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12120 KB Output is correct
2 Correct 4 ms 12124 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 6 ms 12236 KB Output is correct
5 Correct 5 ms 12124 KB Output is correct
6 Correct 5 ms 12120 KB Output is correct
7 Correct 5 ms 12124 KB Output is correct
8 Correct 5 ms 12124 KB Output is correct
9 Correct 5 ms 12124 KB Output is correct
10 Correct 5 ms 12124 KB Output is correct
11 Correct 5 ms 12124 KB Output is correct
12 Correct 5 ms 12124 KB Output is correct
13 Correct 5 ms 12120 KB Output is correct
14 Correct 5 ms 12124 KB Output is correct
15 Correct 5 ms 12124 KB Output is correct
16 Correct 5 ms 12124 KB Output is correct
17 Incorrect 5 ms 12124 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Correct 5 ms 12152 KB Output is correct
3 Correct 307 ms 68364 KB Output is correct
4 Correct 453 ms 84576 KB Output is correct
5 Correct 160 ms 74064 KB Output is correct
6 Correct 153 ms 69712 KB Output is correct
7 Correct 161 ms 74064 KB Output is correct
8 Incorrect 361 ms 80900 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 25692 KB Output is correct
2 Incorrect 2324 ms 308352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 25692 KB Output is correct
2 Incorrect 2324 ms 308352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12120 KB Output is correct
2 Correct 4 ms 12124 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 6 ms 12236 KB Output is correct
5 Correct 5 ms 12124 KB Output is correct
6 Correct 5 ms 12120 KB Output is correct
7 Correct 5 ms 12124 KB Output is correct
8 Correct 5 ms 12124 KB Output is correct
9 Correct 5 ms 12124 KB Output is correct
10 Correct 5 ms 12124 KB Output is correct
11 Correct 5 ms 12124 KB Output is correct
12 Correct 5 ms 12124 KB Output is correct
13 Correct 5 ms 12120 KB Output is correct
14 Correct 5 ms 12124 KB Output is correct
15 Correct 5 ms 12124 KB Output is correct
16 Correct 5 ms 12124 KB Output is correct
17 Incorrect 5 ms 12124 KB Output isn't correct
18 Halted 0 ms 0 KB -