oj.uz

Submission #992356

# Submission time Handle Problem Language Result Execution time Memory
992356 2024-06-04T10:06:56 Z MarwenElarbi Sky Walking (IOI19_walk) C++17
10 / 100
 651 ms 325220 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
const int nax=2e6;
vector<pair<int,int>> adj[nax];
vector<long long> dis(nax);
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
    int n=x.size();
    int k=l.size();
    int cnt=n;
    vector<pair<int,pair<int,int>>> tab(k);
    for (int i = 0; i < k; ++i)
    {
        tab[i]={y[i],{l[i],r[i]}};
    }
    sort(tab.begin(),tab.end());
    map<int,pair<int,int>> mp;
    for (int i = 0; i < n; ++i)
    {
        mp[x[i]]={i,0};
    }
    for (int i = 0; i < k; ++i)
    {
        for (int j = tab[i].se.fi; j <= tab[i].se.se; ++j)
        {
            if(tab[i].fi<=h[j]){
                adj[cnt].pb({mp[x[j]].fi,tab[i].fi-mp[x[j]].se});
                adj[mp[x[j]].fi].pb({cnt,tab[i].fi-mp[x[j]].se});
                mp[x[j]]={cnt,tab[i].fi};
            }
            if(j>tab[i].se.fi){
                adj[cnt].pb({cnt-1,x[j]-x[j-1]});
                adj[cnt-1].pb({cnt,x[j]-x[j-1]});
            }
            cnt++;
        }
    }
    for (int i = 0; i < cnt; ++i)
    {
        dis[i]=1e18;
    }
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
    pq.push({0,s});
    dis[s]=0;
    //cout <<"hey"<<endl;
    //int t=5;
    while(!pq.empty()){
        //cout <<t<<endl;
        //if(t==0) break;
        //t--;
        ll d=pq.top().fi;
        ll x=pq.top().se;
        //cout <<x<<" "<<d<<endl;
        pq.pop();
        if(x==g){
            return d;
        }
        if(dis[x]!=d) continue;
        for(auto u:adj[x]){
            //cout <<"n "<<u.fi<<endl;
            ll newd=u.se+d;
            //cout <<u.se<<endl;
            if(newd>=dis[u.fi]) continue;
            dis[u.fi]=newd;
            pq.push({newd,u.fi});
        }
    }
    return -1;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 63068 KB Output is correct
2 Correct 13 ms 63068 KB Output is correct
3 Correct 10 ms 63064 KB Output is correct
4 Correct 11 ms 63068 KB Output is correct
5 Correct 10 ms 63068 KB Output is correct
6 Correct 11 ms 63068 KB Output is correct
7 Correct 11 ms 63064 KB Output is correct
8 Correct 11 ms 63068 KB Output is correct
9 Correct 11 ms 62884 KB Output is correct
10 Correct 12 ms 63068 KB Output is correct
11 Correct 11 ms 63068 KB Output is correct
12 Correct 11 ms 63068 KB Output is correct
13 Correct 11 ms 62876 KB Output is correct
14 Correct 11 ms 63048 KB Output is correct
15 Correct 11 ms 63068 KB Output is correct
16 Correct 11 ms 63064 KB Output is correct
17 Correct 11 ms 63108 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 63064 KB Output is correct
2 Correct 12 ms 63064 KB Output is correct
3 Correct 390 ms 103600 KB Output is correct
4 Correct 651 ms 112832 KB Output is correct
5 Runtime error 476 ms 286452 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 70740 KB Output is correct
2 Runtime error 610 ms 325220 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 57 ms 70740 KB Output is correct
2 Runtime error 610 ms 325220 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 12 ms 63068 KB Output is correct
2 Correct 13 ms 63068 KB Output is correct
3 Correct 10 ms 63064 KB Output is correct
4 Correct 11 ms 63068 KB Output is correct
5 Correct 10 ms 63068 KB Output is correct
6 Correct 11 ms 63068 KB Output is correct
7 Correct 11 ms 63064 KB Output is correct
8 Correct 11 ms 63068 KB Output is correct
9 Correct 11 ms 62884 KB Output is correct
10 Correct 12 ms 63068 KB Output is correct
11 Correct 11 ms 63068 KB Output is correct
12 Correct 11 ms 63068 KB Output is correct
13 Correct 11 ms 62876 KB Output is correct
14 Correct 11 ms 63048 KB Output is correct
15 Correct 11 ms 63068 KB Output is correct
16 Correct 11 ms 63064 KB Output is correct
17 Correct 11 ms 63108 KB Output is correct
18 Correct 11 ms 63064 KB Output is correct
19 Correct 12 ms 63064 KB Output is correct
20 Correct 390 ms 103600 KB Output is correct
21 Correct 651 ms 112832 KB Output is correct
22 Runtime error 476 ms 286452 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -