oj.uz

Submission #812889

# Submission time Handle Problem Language Result Execution time Memory
812889 2023-08-07T11:37:54 Z fatemetmhr Sky Walking (IOI19_walk) C++17
0 / 100
 803 ms 653256 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 = 1e7 + 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 242 ms 548148 KB Output is correct
2 Correct 225 ms 548204 KB Output is correct
3 Incorrect 226 ms 548144 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 548152 KB Output is correct
2 Correct 222 ms 548156 KB Output is correct
3 Correct 684 ms 621536 KB Output is correct
4 Correct 648 ms 627296 KB Output is correct
5 Correct 416 ms 615196 KB Output is correct
6 Correct 412 ms 608380 KB Output is correct
7 Correct 419 ms 615364 KB Output is correct
8 Correct 803 ms 638920 KB Output is correct
9 Correct 469 ms 617352 KB Output is correct
10 Correct 766 ms 653256 KB Output is correct
11 Correct 489 ms 593236 KB Output is correct
12 Correct 388 ms 584268 KB Output is correct
13 Correct 718 ms 642648 KB Output is correct
14 Correct 371 ms 580628 KB Output is correct
15 Incorrect 488 ms 580772 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 548148 KB Output is correct
2 Correct 225 ms 548204 KB Output is correct
3 Incorrect 226 ms 548144 KB Output isn't correct
4 Halted 0 ms 0 KB -