oj.uz

Submission #992361

# Submission time Handle Problem Language Result Execution time Memory
992361 2024-06-04T10:10:23 Z MarwenElarbi Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 1048576 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=8e6;
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;
}

/*int main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int n, m;
    assert(2 == scanf("%d%d", &n, &m));
    vector<int> x(n), h(n);
    for (int i = 0; i < n; i++)
        assert(2 == scanf("%d%d", &x[i], &h[i]));
    vector<int> l(m), r(m), y(m);
    for (int i = 0; i < m; i++)
        assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
    int s, g;
    assert(2 == scanf("%d%d", &s, &g));
    fclose(stdin);

    long long result = min_distance(x, h, l, r, y, s, g);

    printf("%lld\n", result);
    fclose(stdout);
    return 0;
}*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 250864 KB Output is correct
2 Correct 39 ms 250708 KB Output is correct
3 Correct 38 ms 250868 KB Output is correct
4 Correct 36 ms 250704 KB Output is correct
5 Correct 36 ms 250704 KB Output is correct
6 Correct 44 ms 250736 KB Output is correct
7 Correct 42 ms 250708 KB Output is correct
8 Correct 40 ms 250716 KB Output is correct
9 Correct 39 ms 250708 KB Output is correct
10 Correct 38 ms 250968 KB Output is correct
11 Correct 36 ms 250704 KB Output is correct
12 Correct 37 ms 250708 KB Output is correct
13 Correct 42 ms 250716 KB Output is correct
14 Correct 39 ms 250708 KB Output is correct
15 Correct 40 ms 250716 KB Output is correct
16 Correct 38 ms 250704 KB Output is correct
17 Correct 40 ms 250964 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 250704 KB Output is correct
2 Correct 36 ms 250716 KB Output is correct
3 Correct 409 ms 291412 KB Output is correct
4 Correct 703 ms 300720 KB Output is correct
5 Runtime error 1151 ms 1046868 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 84 ms 258644 KB Output is correct
2 Correct 1662 ms 494868 KB Output is correct
3 Execution timed out 5340 ms 1048576 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 258644 KB Output is correct
2 Correct 1662 ms 494868 KB Output is correct
3 Execution timed out 5340 ms 1048576 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 250864 KB Output is correct
2 Correct 39 ms 250708 KB Output is correct
3 Correct 38 ms 250868 KB Output is correct
4 Correct 36 ms 250704 KB Output is correct
5 Correct 36 ms 250704 KB Output is correct
6 Correct 44 ms 250736 KB Output is correct
7 Correct 42 ms 250708 KB Output is correct
8 Correct 40 ms 250716 KB Output is correct
9 Correct 39 ms 250708 KB Output is correct
10 Correct 38 ms 250968 KB Output is correct
11 Correct 36 ms 250704 KB Output is correct
12 Correct 37 ms 250708 KB Output is correct
13 Correct 42 ms 250716 KB Output is correct
14 Correct 39 ms 250708 KB Output is correct
15 Correct 40 ms 250716 KB Output is correct
16 Correct 38 ms 250704 KB Output is correct
17 Correct 40 ms 250964 KB Output is correct
18 Correct 41 ms 250704 KB Output is correct
19 Correct 36 ms 250716 KB Output is correct
20 Correct 409 ms 291412 KB Output is correct
21 Correct 703 ms 300720 KB Output is correct
22 Runtime error 1151 ms 1046868 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -