oj.uz

Submission #960809

# Submission time Handle Problem Language Result Execution time Memory
960809 2024-04-11T04:39:57 Z _rain_ Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 197 ms 53844 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
{
	bool check()
	{
		return n <= (int)2e3 && numperson <= (int)2e3;
	}
	const int N = (int)2e3;
	int cost[N + 2][N + 2];
	int d[N + 2] ;
	vector<int> g[N + 2];
	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]]);
	}
}
namespace subtask2
{
	bool check(void)
	{
		return true;
	}
	const int N = (int)2e3;
	vector<int> g[N + 2];
	vector<int> divisor[N + 2];
	int cost[N + 2][N + 2];
	bool ok[N + 2][N + 2];
	int d[N + 2];
	void prepare(void)
	{
		for (int i = 1; i <= numperson; ++i)
			ok[b[i]][p[i]] = true;

		for (int i = 1; i <= trunc(sqrt(N)); ++i)
		{
			divisor[i * i].emplace_back(i);
			for (int j = i + 1; j <= N / i; ++j)
			{
				divisor[i * j].emplace_back(i);
				divisor[i * j].emplace_back(j);
			}
		}
		for (int i = 1; i <= N; ++i) sort(divisor[i].begin() , divisor[i].end() , greater<int>());
		return;
	}

	void main_code(void)
	{
		prepare();
		memset(cost , 0x3f , sizeof cost);
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (i != j) 
					{
						int dist = abs(i - j);
						for (auto& v : divisor[dist])
						{
							if (ok[i][v])
							{
								g[i].emplace_back(j);
								cost[i][j] = dist / v;
								break;
							}
						}
						for (auto& v : divisor[dist])
						{
							if (ok[j][v])
							{
								g[j].emplace_back(i);
								cost[j][i] = dist / v;
								break;
							}
						}
					}
			}
		}
		memset(d , 0x3f , sizeof d);
		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;
	if (subtask2::check())
		return subtask2::main_code() , 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17244 KB Output is correct
2 Correct 3 ms 17244 KB Output is correct
3 Correct 3 ms 17396 KB Output is correct
4 Correct 3 ms 17244 KB Output is correct
5 Correct 3 ms 17244 KB Output is correct
6 Correct 3 ms 17244 KB Output is correct
7 Correct 3 ms 17244 KB Output is correct
8 Correct 3 ms 17240 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 5 ms 17244 KB Output is correct
11 Correct 42 ms 18872 KB Output is correct
12 Correct 6 ms 17660 KB Output is correct
13 Correct 15 ms 20688 KB Output is correct
14 Correct 38 ms 17496 KB Output is correct
15 Correct 38 ms 17784 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17244 KB Output is correct
2 Correct 3 ms 17244 KB Output is correct
3 Correct 3 ms 17244 KB Output is correct
4 Correct 3 ms 17244 KB Output is correct
5 Correct 3 ms 17112 KB Output is correct
6 Correct 3 ms 17244 KB Output is correct
7 Correct 3 ms 17244 KB Output is correct
8 Correct 3 ms 17244 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 4 ms 17244 KB Output is correct
11 Correct 42 ms 19028 KB Output is correct
12 Correct 6 ms 17540 KB Output is correct
13 Correct 17 ms 20808 KB Output is correct
14 Correct 38 ms 17500 KB Output is correct
15 Correct 38 ms 17756 KB Output is correct
16 Correct 10 ms 17500 KB Output is correct
17 Correct 33 ms 17748 KB Output is correct
18 Correct 12 ms 17244 KB Output is correct
19 Correct 6 ms 17136 KB Output is correct
20 Correct 189 ms 49456 KB Output is correct
21 Correct 15 ms 17240 KB Output is correct
22 Correct 8 ms 17244 KB Output is correct
23 Correct 12 ms 17500 KB Output is correct
24 Correct 35 ms 17244 KB Output is correct
25 Correct 38 ms 17356 KB Output is correct
26 Correct 20 ms 23260 KB Output is correct
27 Correct 16 ms 19288 KB Output is correct
28 Correct 41 ms 17444 KB Output is correct
29 Correct 8 ms 17244 KB Output is correct
30 Correct 3 ms 17244 KB Output is correct
31 Correct 6 ms 17140 KB Output is correct
32 Correct 5 ms 17244 KB Output is correct
33 Correct 38 ms 17468 KB Output is correct
34 Correct 37 ms 17496 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17244 KB Output is correct
2 Correct 3 ms 17244 KB Output is correct
3 Correct 2 ms 17244 KB Output is correct
4 Correct 5 ms 17244 KB Output is correct
5 Correct 3 ms 17244 KB Output is correct
6 Correct 3 ms 17244 KB Output is correct
7 Correct 3 ms 17132 KB Output is correct
8 Correct 3 ms 17240 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 5 ms 17244 KB Output is correct
11 Correct 42 ms 19200 KB Output is correct
12 Correct 6 ms 17660 KB Output is correct
13 Correct 15 ms 20788 KB Output is correct
14 Correct 38 ms 17496 KB Output is correct
15 Correct 38 ms 17756 KB Output is correct
16 Correct 10 ms 17500 KB Output is correct
17 Correct 33 ms 17752 KB Output is correct
18 Correct 12 ms 17244 KB Output is correct
19 Correct 5 ms 17244 KB Output is correct
20 Correct 197 ms 49616 KB Output is correct
21 Correct 15 ms 17240 KB Output is correct
22 Correct 7 ms 17244 KB Output is correct
23 Correct 12 ms 17244 KB Output is correct
24 Correct 35 ms 17420 KB Output is correct
25 Correct 38 ms 17240 KB Output is correct
26 Correct 19 ms 23264 KB Output is correct
27 Correct 14 ms 19416 KB Output is correct
28 Correct 40 ms 17400 KB Output is correct
29 Correct 8 ms 17244 KB Output is correct
30 Correct 3 ms 17244 KB Output is correct
31 Correct 6 ms 17244 KB Output is correct
32 Correct 5 ms 17244 KB Output is correct
33 Correct 38 ms 17652 KB Output is correct
34 Correct 39 ms 17632 KB Output is correct
35 Correct 53 ms 23040 KB Output is correct
36 Correct 25 ms 21336 KB Output is correct
37 Correct 119 ms 24844 KB Output is correct
38 Correct 104 ms 23888 KB Output is correct
39 Correct 108 ms 24144 KB Output is correct
40 Correct 111 ms 24148 KB Output is correct
41 Correct 102 ms 23832 KB Output is correct
42 Correct 86 ms 21468 KB Output is correct
43 Correct 85 ms 21340 KB Output is correct
44 Correct 179 ms 53764 KB Output is correct
45 Correct 96 ms 24144 KB Output is correct
46 Correct 85 ms 24148 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17240 KB Output is correct
2 Correct 3 ms 17244 KB Output is correct
3 Correct 2 ms 17244 KB Output is correct
4 Correct 3 ms 17132 KB Output is correct
5 Correct 3 ms 17244 KB Output is correct
6 Correct 3 ms 17244 KB Output is correct
7 Correct 3 ms 17244 KB Output is correct
8 Correct 3 ms 17244 KB Output is correct
9 Correct 3 ms 17124 KB Output is correct
10 Correct 5 ms 17244 KB Output is correct
11 Correct 44 ms 19036 KB Output is correct
12 Correct 6 ms 17660 KB Output is correct
13 Correct 15 ms 20688 KB Output is correct
14 Correct 37 ms 17500 KB Output is correct
15 Correct 38 ms 17624 KB Output is correct
16 Correct 10 ms 17496 KB Output is correct
17 Correct 33 ms 17816 KB Output is correct
18 Correct 11 ms 17240 KB Output is correct
19 Correct 5 ms 17240 KB Output is correct
20 Correct 182 ms 49592 KB Output is correct
21 Correct 15 ms 17244 KB Output is correct
22 Correct 7 ms 17240 KB Output is correct
23 Correct 11 ms 17244 KB Output is correct
24 Correct 35 ms 17392 KB Output is correct
25 Correct 38 ms 17360 KB Output is correct
26 Correct 19 ms 23264 KB Output is correct
27 Correct 14 ms 19416 KB Output is correct
28 Correct 40 ms 17404 KB Output is correct
29 Correct 8 ms 17240 KB Output is correct
30 Correct 3 ms 17244 KB Output is correct
31 Correct 6 ms 17244 KB Output is correct
32 Correct 5 ms 17244 KB Output is correct
33 Correct 38 ms 17576 KB Output is correct
34 Correct 38 ms 17524 KB Output is correct
35 Correct 54 ms 23108 KB Output is correct
36 Correct 24 ms 21340 KB Output is correct
37 Correct 109 ms 24640 KB Output is correct
38 Correct 101 ms 23972 KB Output is correct
39 Correct 120 ms 24508 KB Output is correct
40 Correct 106 ms 24132 KB Output is correct
41 Correct 106 ms 23916 KB Output is correct
42 Correct 87 ms 21340 KB Output is correct
43 Correct 95 ms 21424 KB Output is correct
44 Correct 175 ms 53844 KB Output is correct
45 Correct 93 ms 24092 KB Output is correct
46 Correct 88 ms 24224 KB Output is correct
47 Runtime error 29 ms 51540 KB Execution killed with signal 6
48 Halted 0 ms 0 KB -