oj.uz

Submission #955095

# Submission time Handle Problem Language Result Execution time Memory
955095 2024-03-29T11:25:54 Z waldi Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 652032 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);
		}
	}
	ll wyn = odl[meta];
	return wyn<inf ? wyn : -1ll;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 392 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 440 KB Output is correct
16 Correct 0 ms 352 KB Output is correct
17 Correct 1 ms 360 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 868 ms 111196 KB Output is correct
4 Correct 772 ms 121080 KB Output is correct
5 Correct 491 ms 105448 KB Output is correct
6 Correct 415 ms 91240 KB Output is correct
7 Correct 523 ms 105204 KB Output is correct
8 Correct 1180 ms 145076 KB Output is correct
9 Correct 635 ms 105872 KB Output is correct
10 Correct 1109 ms 171500 KB Output is correct
11 Correct 420 ms 63028 KB Output is correct
12 Correct 249 ms 41148 KB Output is correct
13 Correct 901 ms 150928 KB Output is correct
14 Correct 167 ms 41204 KB Output is correct
15 Correct 217 ms 40440 KB Output is correct
16 Correct 200 ms 42488 KB Output is correct
17 Correct 222 ms 41100 KB Output is correct
18 Correct 180 ms 44536 KB Output is correct
19 Correct 5 ms 2200 KB Output is correct
20 Correct 55 ms 19920 KB Output is correct
21 Correct 212 ms 40692 KB Output is correct
22 Correct 206 ms 41464 KB Output is correct
23 Correct 194 ms 51308 KB Output is correct
24 Correct 234 ms 41776 KB Output is correct
25 Correct 205 ms 40784 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 11576 KB Output is correct
2 Execution timed out 4035 ms 652032 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 11576 KB Output is correct
2 Execution timed out 4035 ms 652032 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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 392 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 440 KB Output is correct
16 Correct 0 ms 352 KB Output is correct
17 Correct 1 ms 360 KB Output is correct
18 Correct 1 ms 356 KB Output is correct
19 Correct 0 ms 352 KB Output is correct
20 Correct 868 ms 111196 KB Output is correct
21 Correct 772 ms 121080 KB Output is correct
22 Correct 491 ms 105448 KB Output is correct
23 Correct 415 ms 91240 KB Output is correct
24 Correct 523 ms 105204 KB Output is correct
25 Correct 1180 ms 145076 KB Output is correct
26 Correct 635 ms 105872 KB Output is correct
27 Correct 1109 ms 171500 KB Output is correct
28 Correct 420 ms 63028 KB Output is correct
29 Correct 249 ms 41148 KB Output is correct
30 Correct 901 ms 150928 KB Output is correct
31 Correct 167 ms 41204 KB Output is correct
32 Correct 217 ms 40440 KB Output is correct
33 Correct 200 ms 42488 KB Output is correct
34 Correct 222 ms 41100 KB Output is correct
35 Correct 180 ms 44536 KB Output is correct
36 Correct 5 ms 2200 KB Output is correct
37 Correct 55 ms 19920 KB Output is correct
38 Correct 212 ms 40692 KB Output is correct
39 Correct 206 ms 41464 KB Output is correct
40 Correct 194 ms 51308 KB Output is correct
41 Correct 234 ms 41776 KB Output is correct
42 Correct 205 ms 40784 KB Output is correct
43 Correct 47 ms 11576 KB Output is correct
44 Execution timed out 4035 ms 652032 KB Time limit exceeded
45 Halted 0 ms 0 KB -