oj.uz

Submission #1077122

# Submission time Handle Problem Language Result Execution time Memory
1077122 2024-08-27T01:16:30 Z HD1 Sky Walking (IOI19_walk) C++14
10 / 100
 1343 ms 347744 KB 
#include "walk.h"
#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define sz(x) ll(x.size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAX=1e6+10;
const ll inf=1e18;
vector<ii>gfo[MAX];
ll cur[MAX], dist[MAX];
void dikstra(ll ini){
    set<ii> q;
    q.insert({0,ini});
    dist[ini]=0;
    while(sz(q)){
        auto x=*q.begin();
        q.erase(q.begin());
        ll u=x.ss;
        ll dist_u=x.ff;
        if(dist_u!=dist[u])continue;
        for(auto y:gfo[u]){
            ll w=y.ss;
            ll v=y.ff;
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                q.insert({dist[v], v});
            }
        }
    }
}
map< pair<ll,ll>, ll> M;
set<ll> torre;
long long min_distance(vector<int> x,vector<int> h,
    vector<int> l,vector<int> r, 
    vector<int> y, int s, int g) {
    vector<pair<int,ii>> c;
    ll m=sz(y);//numero de rascacielos
    ll n=sz(x);//numero de torres
    for(ll i=0; i<m; i++){
        c.pb({y[i],{l[i],r[i]}});// por su altura
    }
    for(ll i=0; i<n; i++){
        torre.insert(i);
    }
    sort(all(c));
    ll nod=0, nod_prev=0, mx=0, pos=0;
    for(ll i=0; i<n; i++){
        if(!M.count({x[i], 0})){
            M[{x[i],0}]=mx+1;
            mx++;
            cur[i]=0;//altura
        }
    }
    //cout<<mx<<'\n';
    vector<ll>ers;
    for(auto q:c){//rascacielo en la altura q.ff
        ll alt=q.ff;
        ll l=q.ss.ff, r=q.ss.ss;
        //cout<<l<<' '<<r<<'\n';
        if(!sz(torre))continue;
        for(auto it=torre.lower_bound(l); it!=torre.end() && it!=torre.upper_bound(r); it++){
            //cout<<*it<<'\n';
            //cout<<alt<<' '<<h[*it]<<' '<<*it<<'\n';
            if(alt<=h[*it]){// hay interseccion
                //cout<<"quepasa"<<'\n';
                if(!M.count({x[*it],alt})){//creamos el nodo
                    M[{x[*it],alt}]=mx+1;
                    mx++;
                }
                //cout<<"normal "<<*it<<'\n';
                nod=M[{x[*it],alt}];
                // vertical
                gfo[nod].pb({M[{x[*it], cur[*it]}],alt-cur[*it]});
                gfo[M[{x[*it], cur[*it]}]].pb({nod,alt-cur[*it]});
                cur[*it]=alt;
                if(*it==l){
                    nod_prev=nod;
                    pos=x[*it];
                    continue;
                }
                //horizontal
                //cout<<"normal2 "<<*it<<'\n';
                gfo[nod].pb({nod_prev, x[*it]-pos});
                gfo[nod_prev].pb({nod, x[*it]-pos});
                nod_prev=nod;
                pos=x[*it];
            }
            else {
                ers.pb(*it);
            }
        }
        for(ll w:ers){
            torre.erase(torre.find(w));
        }
        ers.clear();
    }
    // cout<<"muereeeeee"<<'\n';
    // for(auto a:M){
    //  cout<<a.ff.ff<<' '<<a.ff.ss<<" -> "<<a.ss<<'\n';
    // }
    // for(auto a:M){
    //  cout<<a.ss<<" -> ";
    //  for(auto b:gfo[a.ss]){
    //      cout<<b.ff<<", "<<b.ss;
    //      cout<<'\n';
    //  }
    //  cout<<'\n';
    // }
    for(ll i=0; i<=mx; i++)dist[i]=inf;
    dikstra(M[{x[s],0}]);
    ll ans=dist[M[{x[g],0}]];
    if(ans==inf)ans=-1;
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24924 KB Output is correct
2 Correct 10 ms 23896 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 11 ms 23896 KB Output is correct
5 Correct 11 ms 25108 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 10 ms 23900 KB Output is correct
8 Correct 12 ms 23900 KB Output is correct
9 Correct 11 ms 23756 KB Output is correct
10 Correct 10 ms 23900 KB Output is correct
11 Correct 11 ms 23900 KB Output is correct
12 Correct 11 ms 23896 KB Output is correct
13 Correct 10 ms 24900 KB Output is correct
14 Correct 10 ms 23900 KB Output is correct
15 Correct 11 ms 23900 KB Output is correct
16 Correct 11 ms 23896 KB Output is correct
17 Correct 11 ms 23896 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 10 ms 24920 KB Output is correct
3 Correct 1049 ms 136208 KB Output is correct
4 Correct 1204 ms 151340 KB Output is correct
5 Correct 794 ms 131804 KB Output is correct
6 Correct 708 ms 119972 KB Output is correct
7 Correct 847 ms 131896 KB Output is correct
8 Correct 1336 ms 166084 KB Output is correct
9 Correct 891 ms 132036 KB Output is correct
10 Runtime error 1343 ms 347744 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 40372 KB Output is correct
2 Runtime error 1048 ms 344812 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 93 ms 40372 KB Output is correct
2 Runtime error 1048 ms 344812 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 10 ms 24924 KB Output is correct
2 Correct 10 ms 23896 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 11 ms 23896 KB Output is correct
5 Correct 11 ms 25108 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 10 ms 23900 KB Output is correct
8 Correct 12 ms 23900 KB Output is correct
9 Correct 11 ms 23756 KB Output is correct
10 Correct 10 ms 23900 KB Output is correct
11 Correct 11 ms 23900 KB Output is correct
12 Correct 11 ms 23896 KB Output is correct
13 Correct 10 ms 24900 KB Output is correct
14 Correct 10 ms 23900 KB Output is correct
15 Correct 11 ms 23900 KB Output is correct
16 Correct 11 ms 23896 KB Output is correct
17 Correct 11 ms 23896 KB Output is correct
18 Correct 11 ms 23896 KB Output is correct
19 Correct 10 ms 24920 KB Output is correct
20 Correct 1049 ms 136208 KB Output is correct
21 Correct 1204 ms 151340 KB Output is correct
22 Correct 794 ms 131804 KB Output is correct
23 Correct 708 ms 119972 KB Output is correct
24 Correct 847 ms 131896 KB Output is correct
25 Correct 1336 ms 166084 KB Output is correct
26 Correct 891 ms 132036 KB Output is correct
27 Runtime error 1343 ms 347744 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -