oj.uz

Submission #1075386

# Submission time Handle Problem Language Result Execution time Memory
1075386 2024-08-26T04:58:41 Z HD1 Sky Walking (IOI19_walk) C++14
10 / 100
 1239 ms 344324 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;
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
	}
	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
		}
	}
	for(auto q:c){//rascacielo en la altura q.ff
		ll alt=q.ff;
		ll l=q.ss.ff;
		ll r=q.ss.ss;
		for(ll i=l; i<=r; i++){
			if(alt<=h[i]){// hay interseccion 
				if(!M.count({x[i],alt})){
					M[{x[i],alt}]=mx+1;
					mx++;
				}
				nod = M[{x[i], alt}];
				// verical
				gfo[nod].pb({M[{x[i],cur[i]}], alt-cur[i]});
				gfo[M[{x[i],cur[i]}]].pb({nod, alt-cur[i]});
				cur[i]=alt; 
				if(i==l){
					nod_prev=nod;
					pos=x[l];
					continue;
				}
				//horizontal
				gfo[nod].pb({nod_prev,x[i]-pos});
				gfo[nod_prev].pb({nod,x[i]-pos});
				pos = x[i];// ultima posicion de interseccion
				nod_prev = nod;// nombre del nodo anterior
			}
		}
	}
	// 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 23896 KB Output is correct
2 Correct 11 ms 23896 KB Output is correct
3 Correct 11 ms 23900 KB Output is correct
4 Correct 9 ms 23900 KB Output is correct
5 Correct 11 ms 24028 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 12 ms 23900 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 10 ms 24000 KB Output is correct
11 Correct 11 ms 23900 KB Output is correct
12 Correct 10 ms 23896 KB Output is correct
13 Correct 10 ms 23900 KB Output is correct
14 Correct 10 ms 23896 KB Output is correct
15 Correct 10 ms 23896 KB Output is correct
16 Correct 9 ms 23920 KB Output is correct
17 Correct 10 ms 23900 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23828 KB Output is correct
3 Correct 918 ms 135328 KB Output is correct
4 Correct 1035 ms 146100 KB Output is correct
5 Correct 716 ms 129984 KB Output is correct
6 Correct 992 ms 118356 KB Output is correct
7 Correct 675 ms 130240 KB Output is correct
8 Correct 1239 ms 165828 KB Output is correct
9 Correct 775 ms 130352 KB Output is correct
10 Runtime error 1147 ms 340932 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 72 ms 39880 KB Output is correct
2 Runtime error 1040 ms 344324 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 72 ms 39880 KB Output is correct
2 Runtime error 1040 ms 344324 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 23896 KB Output is correct
2 Correct 11 ms 23896 KB Output is correct
3 Correct 11 ms 23900 KB Output is correct
4 Correct 9 ms 23900 KB Output is correct
5 Correct 11 ms 24028 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 12 ms 23900 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 10 ms 24000 KB Output is correct
11 Correct 11 ms 23900 KB Output is correct
12 Correct 10 ms 23896 KB Output is correct
13 Correct 10 ms 23900 KB Output is correct
14 Correct 10 ms 23896 KB Output is correct
15 Correct 10 ms 23896 KB Output is correct
16 Correct 9 ms 23920 KB Output is correct
17 Correct 10 ms 23900 KB Output is correct
18 Correct 10 ms 23900 KB Output is correct
19 Correct 10 ms 23828 KB Output is correct
20 Correct 918 ms 135328 KB Output is correct
21 Correct 1035 ms 146100 KB Output is correct
22 Correct 716 ms 129984 KB Output is correct
23 Correct 992 ms 118356 KB Output is correct
24 Correct 675 ms 130240 KB Output is correct
25 Correct 1239 ms 165828 KB Output is correct
26 Correct 775 ms 130352 KB Output is correct
27 Runtime error 1147 ms 340932 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -