oj.uz

Submission #679784

# Submission time Handle Problem Language Result Execution time Memory
679784 2023-01-09T08:06:01 Z parsadox2 Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 1 ms 984 KB 
#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e4 + 10 , maxsq = 175 , inf = 1e9 + 10;
int n , b[maxn] , p[maxn] , m , dis[maxn][maxsq + 10] , ans;
bool marked[maxn][maxsq + 10];
vector <int> all[maxn];
priority_queue <pair <int , pair <int , int>>> st;

void add(int v , int j , int val)
{
	if(dis[v][j] > val)
	{
		dis[v][j] = val;
		st.push({dis[v][j] , {v , j}});
	}
}

void jmp_small(int D , int now , int jmp)
{
	if(now + jmp < n)
		add(now + jmp , jmp , D + 1);
	if(now - jmp > -1)
		add(now - jmp , jmp , D + 1);
}

void jmp_big(int D , int now , int jmp)
{
	for(int tmp = now + jmp ; tmp < n ; tmp += jmp)
		add(tmp , maxsq , D + ((tmp - now) / jmp));
	for(int tmp = now - jmp ; tmp > -1 ; tmp -= jmp)
		add(tmp , maxsq , D + ((now - tmp) / jmp));
}

void update(int D , int now , int jmp)
{
	if(marked[now][jmp])
		return;
	marked[now][jmp] = true;
	if(jmp != maxsq)
	{
		jmp_small(D , now , jmp);
		return;
	}
	for(auto u : all[now])
	{
		if(u < maxsq)
			jmp_small(D , now , u);
		else
			jmp_big(D , now , u);
	}
}

void dij()
{
	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j <= maxsq ; j++)
			dis[i][j] = inf;
	dis[b[0]][maxsq] = 0;
	st.push({0 , {b[0] , maxsq}});
	while(!st.empty())
	{
		auto v = st.top();
		st.pop();
		int D = v.F , now = v.S.F , jmp = v.S.S;
		if(now == b[1])
		{
			ans = D;
			break;
		}
		if(!marked[now][maxsq])
		{
			jmp = maxsq;
			update(D , now , jmp);
		}
		jmp = v.S.S;
		update(D , now , jmp);
	}
}	

int32_t main()
{
	fast;
	cin >> n >> m;
	ans = inf;
	for(int i = 0 ; i < m ; i++)
	{
		cin >> b[i] >> p[i];
		all[b[i]].pb(p[i]);
	}
	dij();
	cout << (ans == inf ? -1 : ans) << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 984 KB Output is correct
9 Incorrect 1 ms 980 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Incorrect 1 ms 980 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Incorrect 1 ms 980 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Incorrect 1 ms 980 KB Output isn't correct
10 Halted 0 ms 0 KB -