oj.uz

Submission #960689

# Submission time Handle Problem Language Result Execution time Memory
960689 2024-04-10T23:19:25 Z _rain_ Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 185 ms 48568 KB 
/** author : _RAIN_ **/
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;

#define MASK(x) ((i64)(1) << (x))
#define BIT(mask , x) (((mask) >> (x)) & (1))

template<class T>
	bool maximize(T &a , T b) {if (a < b) return a = b , true; else return false;}
template<class T>
	bool minimize(T &a , T b) {if (a > b) return a = b , true; else return false;}
template<class T>
	T gcd(T x , T y) {while (y) swap(y , x %= y); return x;}
template<class T>
	T lcm(T x , T y) {return (x * y) / gcd(x , y);}

const int maxn = 3e4;
int b[maxn + 2] , p[maxn + 2] , idx[maxn + 2];
int n , numperson;

namespace subtask1
{
	const int N = (int)2e3;
	int cost[N + 2][N + 2];
	int d[N + 2] ;
	vector<int> g[N + 2];
	bool check()
	{
		return n <= (int)2e3 && numperson <= (int)2e3;
	}
	void main_code(void)
	{
		memset(cost , 0x3f , sizeof cost);
		memset(d , 0x3f , sizeof d);
		for (int i = 1; i <= numperson; ++i)
		{
			for (int j = 1; j <= numperson; ++j)
			{
				if (b[i] != b[j])
				{
					int dist = abs(b[i] - b[j]);
					if (dist % p[i] == 0) 
						{
							g[b[i]].emplace_back(b[j]);
							minimize(cost[b[i]][b[j]] , dist / p[i]);
						}
					if (dist % p[j] == 0)
						{
							g[b[j]].emplace_back(b[i]);
							minimize(cost[b[j]][b[i]] , dist / p[j]);
						}
				}
			}
			
		}
		priority_queue<pair<i64 ,int> , vector<pair<i64 , int>> , greater<pair<i64 , int>>> q;
			d[b[1]] = 0;
			q.emplace(d[b[1]] , b[1]);
			while (q.size())
			{
				int u = q.top().second;
				int val = q.top().first; q.pop();
				if (val != d[u]) continue;
				for (int& v : g[u])
				{
					if (minimize(d[v] , d[u] + cost[u][v]))
						q.emplace(d[v] , v);
				}
			}
			cout << (d[b[2]] == d[n + 1] ? -1 : d[b[2]]);
	}
}

int32_t main(void)
{
	cin.tie(nullptr)->sync_with_stdio(false);
	const string name = "main";
	if (fopen((name + ".inp").c_str() , "r"))
	{
		(void)!freopen((name + ".inp").c_str() , "r" , stdin);
		(void)!freopen((name + ".out").c_str() , "w+", stdout);
	}
	cin >> n >> numperson;
	for (int i = 1; i <= numperson; ++i) 
		cin >> b[i] >> p[i];
	if (subtask1::check())
		return subtask1::main_code() , 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15960 KB Output is correct
2 Correct 3 ms 15964 KB Output is correct
3 Correct 3 ms 15964 KB Output is correct
4 Correct 3 ms 15964 KB Output is correct
5 Correct 3 ms 16020 KB Output is correct
6 Correct 3 ms 15964 KB Output is correct
7 Correct 3 ms 15964 KB Output is correct
8 Correct 3 ms 15964 KB Output is correct
9 Correct 3 ms 15964 KB Output is correct
10 Correct 4 ms 16220 KB Output is correct
11 Correct 42 ms 17860 KB Output is correct
12 Correct 6 ms 16476 KB Output is correct
13 Correct 14 ms 19664 KB Output is correct
14 Correct 39 ms 16524 KB Output is correct
15 Correct 38 ms 16636 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15960 KB Output is correct
2 Correct 3 ms 15960 KB Output is correct
3 Correct 3 ms 15964 KB Output is correct
4 Correct 3 ms 16016 KB Output is correct
5 Correct 3 ms 15964 KB Output is correct
6 Correct 3 ms 15964 KB Output is correct
7 Correct 3 ms 15964 KB Output is correct
8 Correct 3 ms 15964 KB Output is correct
9 Correct 3 ms 15960 KB Output is correct
10 Correct 5 ms 16216 KB Output is correct
11 Correct 41 ms 18004 KB Output is correct
12 Correct 6 ms 16472 KB Output is correct
13 Correct 14 ms 19664 KB Output is correct
14 Correct 38 ms 16476 KB Output is correct
15 Correct 38 ms 16548 KB Output is correct
16 Correct 10 ms 16476 KB Output is correct
17 Correct 33 ms 16660 KB Output is correct
18 Correct 12 ms 16252 KB Output is correct
19 Correct 6 ms 16216 KB Output is correct
20 Correct 174 ms 48568 KB Output is correct
21 Correct 15 ms 16216 KB Output is correct
22 Correct 8 ms 16220 KB Output is correct
23 Correct 11 ms 16220 KB Output is correct
24 Correct 35 ms 16220 KB Output is correct
25 Correct 38 ms 16296 KB Output is correct
26 Correct 18 ms 20444 KB Output is correct
27 Correct 14 ms 18392 KB Output is correct
28 Correct 39 ms 16288 KB Output is correct
29 Correct 8 ms 16220 KB Output is correct
30 Correct 3 ms 16220 KB Output is correct
31 Correct 6 ms 16220 KB Output is correct
32 Correct 5 ms 16220 KB Output is correct
33 Correct 38 ms 16620 KB Output is correct
34 Correct 38 ms 16476 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15960 KB Output is correct
2 Correct 3 ms 15964 KB Output is correct
3 Correct 3 ms 15960 KB Output is correct
4 Correct 3 ms 15964 KB Output is correct
5 Correct 3 ms 15960 KB Output is correct
6 Correct 3 ms 15960 KB Output is correct
7 Correct 3 ms 15964 KB Output is correct
8 Correct 3 ms 16216 KB Output is correct
9 Correct 3 ms 15964 KB Output is correct
10 Correct 5 ms 16220 KB Output is correct
11 Correct 42 ms 18004 KB Output is correct
12 Correct 6 ms 16476 KB Output is correct
13 Correct 14 ms 19664 KB Output is correct
14 Correct 38 ms 16648 KB Output is correct
15 Correct 37 ms 16476 KB Output is correct
16 Correct 10 ms 16432 KB Output is correct
17 Correct 33 ms 16768 KB Output is correct
18 Correct 12 ms 16216 KB Output is correct
19 Correct 5 ms 16216 KB Output is correct
20 Correct 185 ms 48492 KB Output is correct
21 Correct 15 ms 16268 KB Output is correct
22 Correct 8 ms 16220 KB Output is correct
23 Correct 11 ms 16220 KB Output is correct
24 Correct 35 ms 16220 KB Output is correct
25 Correct 38 ms 16252 KB Output is correct
26 Correct 18 ms 21820 KB Output is correct
27 Correct 14 ms 18392 KB Output is correct
28 Correct 40 ms 16264 KB Output is correct
29 Correct 8 ms 16220 KB Output is correct
30 Correct 3 ms 15964 KB Output is correct
31 Correct 6 ms 16220 KB Output is correct
32 Correct 5 ms 16220 KB Output is correct
33 Correct 38 ms 16544 KB Output is correct
34 Correct 38 ms 16608 KB Output is correct
35 Incorrect 3 ms 600 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15964 KB Output is correct
2 Correct 3 ms 15960 KB Output is correct
3 Correct 3 ms 15960 KB Output is correct
4 Correct 3 ms 15964 KB Output is correct
5 Correct 3 ms 15964 KB Output is correct
6 Correct 3 ms 15964 KB Output is correct
7 Correct 3 ms 15964 KB Output is correct
8 Correct 3 ms 15964 KB Output is correct
9 Correct 3 ms 15960 KB Output is correct
10 Correct 4 ms 16220 KB Output is correct
11 Correct 42 ms 18044 KB Output is correct
12 Correct 6 ms 16472 KB Output is correct
13 Correct 14 ms 19664 KB Output is correct
14 Correct 38 ms 16476 KB Output is correct
15 Correct 38 ms 16476 KB Output is correct
16 Correct 10 ms 16476 KB Output is correct
17 Correct 34 ms 16684 KB Output is correct
18 Correct 12 ms 16220 KB Output is correct
19 Correct 5 ms 16032 KB Output is correct
20 Correct 170 ms 48452 KB Output is correct
21 Correct 15 ms 16220 KB Output is correct
22 Correct 7 ms 16220 KB Output is correct
23 Correct 11 ms 16232 KB Output is correct
24 Correct 35 ms 16296 KB Output is correct
25 Correct 38 ms 16220 KB Output is correct
26 Correct 18 ms 22240 KB Output is correct
27 Correct 14 ms 18392 KB Output is correct
28 Correct 42 ms 16216 KB Output is correct
29 Correct 8 ms 16216 KB Output is correct
30 Correct 3 ms 15964 KB Output is correct
31 Correct 7 ms 16220 KB Output is correct
32 Correct 5 ms 16220 KB Output is correct
33 Correct 38 ms 16476 KB Output is correct
34 Correct 38 ms 16724 KB Output is correct
35 Incorrect 3 ms 600 KB Output isn't correct
36 Halted 0 ms 0 KB -