oj.uz

Submission #1077121

# Submission time Handle Problem Language Result Execution time Memory
1077121 2024-08-27T01:14:29 Z HD1 Sky Walking (IOI19_walk) C++14
10 / 100
 1353 ms 346184 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';
        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 12 ms 23832 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 11 ms 23900 KB Output is correct
4 Correct 12 ms 23852 KB Output is correct
5 Correct 11 ms 23872 KB Output is correct
6 Correct 11 ms 23836 KB Output is correct
7 Correct 12 ms 23900 KB Output is correct
8 Correct 11 ms 23896 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 12 ms 23900 KB Output is correct
11 Correct 10 ms 23804 KB Output is correct
12 Correct 15 ms 23896 KB Output is correct
13 Correct 9 ms 23900 KB Output is correct
14 Correct 10 ms 23900 KB Output is correct
15 Correct 10 ms 23900 KB Output is correct
16 Correct 10 ms 23820 KB Output is correct
17 Correct 11 ms 23900 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 23924 KB Output is correct
3 Correct 1173 ms 135356 KB Output is correct
4 Correct 1149 ms 149688 KB Output is correct
5 Correct 782 ms 130244 KB Output is correct
6 Correct 696 ms 118468 KB Output is correct
7 Correct 791 ms 130240 KB Output is correct
8 Correct 1353 ms 165068 KB Output is correct
9 Correct 897 ms 130536 KB Output is correct
10 Runtime error 1283 ms 346184 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 87 ms 40324 KB Output is correct
2 Runtime error 1035 ms 344440 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 87 ms 40324 KB Output is correct
2 Runtime error 1035 ms 344440 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 23832 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 11 ms 23900 KB Output is correct
4 Correct 12 ms 23852 KB Output is correct
5 Correct 11 ms 23872 KB Output is correct
6 Correct 11 ms 23836 KB Output is correct
7 Correct 12 ms 23900 KB Output is correct
8 Correct 11 ms 23896 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 12 ms 23900 KB Output is correct
11 Correct 10 ms 23804 KB Output is correct
12 Correct 15 ms 23896 KB Output is correct
13 Correct 9 ms 23900 KB Output is correct
14 Correct 10 ms 23900 KB Output is correct
15 Correct 10 ms 23900 KB Output is correct
16 Correct 10 ms 23820 KB Output is correct
17 Correct 11 ms 23900 KB Output is correct
18 Correct 11 ms 23896 KB Output is correct
19 Correct 10 ms 23924 KB Output is correct
20 Correct 1173 ms 135356 KB Output is correct
21 Correct 1149 ms 149688 KB Output is correct
22 Correct 782 ms 130244 KB Output is correct
23 Correct 696 ms 118468 KB Output is correct
24 Correct 791 ms 130240 KB Output is correct
25 Correct 1353 ms 165068 KB Output is correct
26 Correct 897 ms 130536 KB Output is correct
27 Runtime error 1283 ms 346184 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -