oj.uz

Submission #812874

# Submission time Handle Problem Language Result Execution time Memory
812874 2023-08-07T11:31:49 Z fatemetmhr Sky Walking (IOI19_walk) C++17
0 / 100
 630 ms 218924 KB 
#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


typedef long long ll;

#define mp     make_pair
#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 2e6 + 10;

ll dis[maxn5];
set <pair<ll, int>> have;
map <int, int> av, last;
vector <pair<int, ll>> adj[maxn5];
pair <int, int> ver[maxn5], per[maxn5];
vector <int> req[maxn5];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	int n = x.size();
	int m = l.size();
	int ind = 0, pt = 0;
	for(int i = 0; i < m; i++){
		per[i] = {l[i], i};
	}
	sort(per, per + m);
	int ss, tt;
	for(int i = 0; i < n; i++){
		if(i == s)
			ss = pt;
		if(i == g)
			tt = pt;
		int id = pt;
		ver[pt++] = {x[i], 0};
		for(auto u : req[i]) if(av.find(y[u]) != av.end() && last[y[u]] == u)
			av.erase(av.find(y[u]));
		while(ind < m && per[ind].fi == i){
			req[r[per[ind].se] + 1].pb(per[ind].se);
			//cout << "pt " << pt << ' ' << r[per[ind].se] << endl;
			if(av.find(y[per[ind].se]) != av.end()){
				adj[pt].pb({av[y[per[ind].se]], 0});
				adj[av[y[per[ind].se]]].pb({pt, 0});
				//cout << "here we ssaw " << av[y[per[ind].se]] << ' ' << y[per[ind].se] << ' ' << i << ' ' << pt << endl;
			}
			last[y[per[ind].se]] = per[ind].se;
			av[y[per[ind].se]] = pt;
			ver[pt] = {x[i], y[per[ind].se]};

			pt++;
			ind++;
		}
		//cout << "hmmm " << i << ' ' << id << endl;
		for(auto it = av.begin(); it != av.end() && (it ->fi) <= h[i]; it++){
			ll len = (it ->fi) - ver[id].se;
			int v = av[it -> fi];
			adj[pt].pb({v, x[i] - ver[v].fi});
			adj[v].pb({pt, x[i] - ver[v].fi});
			av[it -> fi] = pt;
			adj[id].pb({pt, len});
			adj[pt].pb({id, len});
			id = pt;
			ver[pt++] = {x[i], it ->fi};
		}
	}

	memset(dis, -1, sizeof dis);
	dis[ss] = 0;
	have.insert({0, ss});
	/*
	cout << "with " << ss << ' ' << tt << endl;
	for(int i = 0; i < pt; i++){
		cout << "*** " << i << ' ' << ver[i].fi << ' ' << ver[i].se << endl;
		for(auto [u, len] : adj[i])
			cout << u << ' ' << len << endl;
	}
	*/
	while(have.size()){
		int v = have.begin() -> se;

		//cout << "ok " << v << ' ' << ver[v].fi << ' ' << ver[v].se << endl;
		have.erase(have.begin());
		for(auto [u, len] : adj[v]) if(dis[v] + len < dis[u] || dis[u] == -1){
			have.erase({dis[u], u});
			//cout << "here " << v << ' ' << u << ' ' << len << endl;
			dis[u] = dis[v] + len;
			have.insert({dis[u], u});
		}
	}
	return dis[tt];
}

Compilation message

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:96:15: warning: 'tt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |  return dis[tt];
      |               ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 109952 KB Output is correct
2 Correct 53 ms 109856 KB Output is correct
3 Incorrect 47 ms 109828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 109812 KB Output is correct
2 Correct 48 ms 109848 KB Output is correct
3 Correct 499 ms 185380 KB Output is correct
4 Correct 466 ms 192852 KB Output is correct
5 Correct 260 ms 180372 KB Output is correct
6 Correct 247 ms 173600 KB Output is correct
7 Correct 266 ms 180568 KB Output is correct
8 Correct 630 ms 202612 KB Output is correct
9 Correct 328 ms 182636 KB Output is correct
10 Correct 595 ms 218924 KB Output is correct
11 Correct 316 ms 157608 KB Output is correct
12 Correct 249 ms 149928 KB Output is correct
13 Correct 523 ms 208308 KB Output is correct
14 Correct 186 ms 145912 KB Output is correct
15 Incorrect 204 ms 145596 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 120908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 120908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 109952 KB Output is correct
2 Correct 53 ms 109856 KB Output is correct
3 Incorrect 47 ms 109828 KB Output isn't correct
4 Halted 0 ms 0 KB -