oj.uz

Submission #955094

# Submission time Handle Problem Language Result Execution time Memory
955094 2024-03-29T11:25:14 Z waldi Sky Walking (IOI19_walk) C++17
0 / 100
 4000 ms 622356 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#define inf 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int e){
	int n = ssize(x);
	int m = ssize(l);
	
	vector<vector<pii>> g;
	vector<map<int, int>> vec_map(n);
	auto konwersja = [&](int poz, int wys){
		if(!vec_map[poz][wys]) g.emplace_back(), vec_map[poz][wys] = ssize(g);
		return vec_map[poz][wys]-1;
	};
	
	int start = konwersja(s, 0);
	int meta = konwersja(e, 0);
	
	vector<pii> akt(n);
	REP(i, n) akt[i] = {h[i], i};
	sort(rall(akt));
	
	vector<pii> polaczenia(m);
	REP(i, m) polaczenia[i] = {y[i], i};
	sort(rall(polaczenia));
	
	int iter = 0;
	set<int> zapalone;
	for(auto [wys, i] : polaczenia){
		while(iter < ssize(akt) && akt[iter].fi >= wys) zapalone.emplace(akt[iter].se), ++iter;
		int lewo = l[i], prawo = r[i];
		for(auto it = zapalone.find(lewo); *it != prawo; it = next(it)){
			int a = konwersja(*it, wys);
			int b = konwersja(*next(it), wys);
			int c = x[*next(it)]-x[*it];
			g[a].emplace_back(b, c);
			g[b].emplace_back(a, c);
			//~ printf("kr: %d %d  %d\n", a, b, c);
		}
	}
	
	for(auto mapa : vec_map){
		pii pop = {-1, -1};
		for(pii ja : mapa){
			if(pop.fi >= 0){
				int a = pop.se-1;
				int b = ja.se-1;
				int c = ja.fi-pop.fi;
				g[a].emplace_back(b, c);
				g[b].emplace_back(a, c);
				//~ printf("kr: %d %d  %d\n", a, b, c);
			}
			pop = ja;
		}
	}
	
	int siz = ssize(g);
	vector<ll> odl(siz, inf);
	priority_queue<pli> pq;
	odl[start] = 0ll, pq.emplace(0ll, start);
	while(ssize(pq)){
		int w = pq.top().se;
		ll c = -pq.top().fi;
		pq.pop();
		if(odl[w] != c) continue;
		for(pii i : g[w]) if(ll t = odl[w]+i.se; t < odl[i.fi]){
			odl[i.fi] = t, pq.emplace(-t, i.fi);
		}
	}
	return odl[meta];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 887 ms 111860 KB Output is correct
4 Correct 752 ms 125056 KB Output is correct
5 Correct 477 ms 107844 KB Output is correct
6 Correct 425 ms 94920 KB Output is correct
7 Incorrect 481 ms 108688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 12296 KB Output is correct
2 Execution timed out 4045 ms 622356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 12296 KB Output is correct
2 Execution timed out 4045 ms 622356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -