oj.uz

Submission #961134

# Submission time Handle Problem Language Result Execution time Memory
961134 2024-04-11T14:27:57 Z _rain_ Jakarta Skyscrapers (APIO15_skyscraper) C++14
100 / 100
 981 ms 56020 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 (int)n <= (int)2e3;
	}
	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]]);
	}
}
namespace subtask3
{
	bool check(void)
	{
		return true;
	}
	const int N = 3e4;
	const int maxnude = 2e3;
	const int lim = 300;
	vector<int> g[N + 2];
	int d[N + 2][lim + 6];
	int dist[N + 2][lim + 6];

	#define Val(x) get<0>(x)
	#define Node(x) get<1>(x)
	#define Add(x) get<2>(x)

	void main_code(void)
	{
		memset(dist , 0x3f , sizeof dist);
		for (int i = 1; i <= numperson; ++i)
			g[b[i]].emplace_back(p[i]);
		// if it power reach more than lim -> brute force and simple djistrak 
		// else take the Djistrak such as subtask 1 + 2
		priority_queue<tuple<i64 , int  , int> , vector<tuple<i64 , int , int>> , greater<tuple<i64 , int , int>>> q;
		if (p[1] <= lim) dist[b[1]][p[1]] = 0 , q.emplace(dist[b[1]][p[1]] , b[1] , p[1]);
			else dist[b[1]][lim + 1] = 0 , q.emplace(dist[b[1]][lim + 1] , b[1] , lim + 1);
		while (q.size())
		{
			tuple<int , int , int> res = q.top(); q.pop();
			int val = Val(res);
			int u = Node(res);
			int p = Add(res);
			if (val != dist[u][p]) continue;
			
			if (p <= lim)
				{
					if (u + p < n && minimize(dist[u + p][p] , dist[u][p] + 1))	
						q.emplace(dist[u + p][p] , u + p , p);
					if (u - p >= 0 && minimize(dist[u - p][p] , dist[u][p] + 1))
						q.emplace(dist[u - p][p] , u - p , p);
				}
			for (auto& add : g[u])
			{
				if (add <= lim)
					{
						if (minimize(dist[u][add] , dist[u][p]))
							q.emplace(dist[u][add] , u, add);
					}
				if (add > lim)
				{
					for (int v = u  , cnt = 0; v < n; v += add , cnt++)	
						if (minimize(dist[v][lim + 1] , dist[u][p] + cnt))
							q.emplace(dist[v][lim + 1] , v , lim + 1);
					for (int v = u  , cnt = 0; v >= 0; v -= add , cnt++)
						if (minimize(dist[v][lim + 1] , dist[u][p] + cnt))
							q.emplace(dist[v][lim + 1] , v , lim + 1);
				}
			}
			//g[u].clear();
		}
		int answer = dist[n][0];
		for (int i = 0 ; i <= lim + 1; ++i)
			minimize(answer , dist[b[2]][i]);
		if (answer == dist[n][0]) answer = -1;
		cout << answer;
		return;
	}
}

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;
	return subtask3::main_code() , 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22108 KB Output is correct
2 Correct 4 ms 22104 KB Output is correct
3 Correct 4 ms 22008 KB Output is correct
4 Correct 4 ms 22108 KB Output is correct
5 Correct 4 ms 22108 KB Output is correct
6 Correct 5 ms 22108 KB Output is correct
7 Correct 3 ms 22108 KB Output is correct
8 Correct 3 ms 22108 KB Output is correct
9 Correct 4 ms 22108 KB Output is correct
10 Correct 7 ms 22108 KB Output is correct
11 Correct 43 ms 23856 KB Output is correct
12 Correct 8 ms 22616 KB Output is correct
13 Correct 16 ms 25600 KB Output is correct
14 Correct 39 ms 22468 KB Output is correct
15 Correct 39 ms 22612 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22104 KB Output is correct
2 Correct 4 ms 22108 KB Output is correct
3 Correct 3 ms 22024 KB Output is correct
4 Correct 4 ms 22112 KB Output is correct
5 Correct 3 ms 22108 KB Output is correct
6 Correct 4 ms 22108 KB Output is correct
7 Correct 4 ms 22104 KB Output is correct
8 Correct 4 ms 22108 KB Output is correct
9 Correct 4 ms 22108 KB Output is correct
10 Correct 5 ms 22108 KB Output is correct
11 Correct 43 ms 23868 KB Output is correct
12 Correct 7 ms 22524 KB Output is correct
13 Correct 15 ms 25488 KB Output is correct
14 Correct 39 ms 22500 KB Output is correct
15 Correct 39 ms 22464 KB Output is correct
16 Correct 11 ms 22364 KB Output is correct
17 Correct 34 ms 22716 KB Output is correct
18 Correct 12 ms 22104 KB Output is correct
19 Correct 6 ms 22108 KB Output is correct
20 Correct 185 ms 54496 KB Output is correct
21 Correct 16 ms 22196 KB Output is correct
22 Correct 8 ms 22188 KB Output is correct
23 Correct 12 ms 22360 KB Output is correct
24 Correct 36 ms 22108 KB Output is correct
25 Correct 39 ms 22260 KB Output is correct
26 Correct 21 ms 28128 KB Output is correct
27 Correct 16 ms 24280 KB Output is correct
28 Correct 41 ms 22332 KB Output is correct
29 Correct 9 ms 22108 KB Output is correct
30 Correct 4 ms 22108 KB Output is correct
31 Correct 6 ms 22104 KB Output is correct
32 Correct 6 ms 22108 KB Output is correct
33 Correct 39 ms 22596 KB Output is correct
34 Correct 40 ms 22360 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22104 KB Output is correct
2 Correct 3 ms 22108 KB Output is correct
3 Correct 4 ms 22108 KB Output is correct
4 Correct 4 ms 22108 KB Output is correct
5 Correct 4 ms 22108 KB Output is correct
6 Correct 5 ms 22108 KB Output is correct
7 Correct 3 ms 22108 KB Output is correct
8 Correct 4 ms 22108 KB Output is correct
9 Correct 4 ms 22004 KB Output is correct
10 Correct 5 ms 22212 KB Output is correct
11 Correct 43 ms 23860 KB Output is correct
12 Correct 8 ms 22524 KB Output is correct
13 Correct 15 ms 25552 KB Output is correct
14 Correct 39 ms 22364 KB Output is correct
15 Correct 39 ms 22632 KB Output is correct
16 Correct 10 ms 22360 KB Output is correct
17 Correct 36 ms 22884 KB Output is correct
18 Correct 13 ms 22260 KB Output is correct
19 Correct 7 ms 22108 KB Output is correct
20 Correct 173 ms 54476 KB Output is correct
21 Correct 17 ms 22104 KB Output is correct
22 Correct 8 ms 22104 KB Output is correct
23 Correct 12 ms 22108 KB Output is correct
24 Correct 36 ms 22288 KB Output is correct
25 Correct 39 ms 22108 KB Output is correct
26 Correct 19 ms 26844 KB Output is correct
27 Correct 15 ms 24280 KB Output is correct
28 Correct 42 ms 22364 KB Output is correct
29 Correct 9 ms 22108 KB Output is correct
30 Correct 4 ms 22108 KB Output is correct
31 Correct 6 ms 22104 KB Output is correct
32 Correct 5 ms 22108 KB Output is correct
33 Correct 39 ms 22612 KB Output is correct
34 Correct 39 ms 22364 KB Output is correct
35 Correct 54 ms 25048 KB Output is correct
36 Correct 26 ms 23384 KB Output is correct
37 Correct 99 ms 26708 KB Output is correct
38 Correct 112 ms 26196 KB Output is correct
39 Correct 108 ms 26452 KB Output is correct
40 Correct 107 ms 26308 KB Output is correct
41 Correct 122 ms 26004 KB Output is correct
42 Correct 100 ms 23908 KB Output is correct
43 Correct 87 ms 23644 KB Output is correct
44 Correct 174 ms 55892 KB Output is correct
45 Correct 108 ms 26192 KB Output is correct
46 Correct 91 ms 24040 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22108 KB Output is correct
2 Correct 4 ms 22108 KB Output is correct
3 Correct 3 ms 22108 KB Output is correct
4 Correct 4 ms 22004 KB Output is correct
5 Correct 4 ms 22104 KB Output is correct
6 Correct 3 ms 22108 KB Output is correct
7 Correct 3 ms 22104 KB Output is correct
8 Correct 4 ms 22108 KB Output is correct
9 Correct 4 ms 22108 KB Output is correct
10 Correct 5 ms 22108 KB Output is correct
11 Correct 42 ms 23904 KB Output is correct
12 Correct 7 ms 22524 KB Output is correct
13 Correct 15 ms 25544 KB Output is correct
14 Correct 39 ms 22364 KB Output is correct
15 Correct 39 ms 22584 KB Output is correct
16 Correct 11 ms 22364 KB Output is correct
17 Correct 34 ms 22660 KB Output is correct
18 Correct 12 ms 22108 KB Output is correct
19 Correct 6 ms 22108 KB Output is correct
20 Correct 160 ms 54356 KB Output is correct
21 Correct 17 ms 22164 KB Output is correct
22 Correct 8 ms 22108 KB Output is correct
23 Correct 12 ms 22108 KB Output is correct
24 Correct 37 ms 22236 KB Output is correct
25 Correct 40 ms 22352 KB Output is correct
26 Correct 19 ms 26844 KB Output is correct
27 Correct 15 ms 24280 KB Output is correct
28 Correct 41 ms 22268 KB Output is correct
29 Correct 9 ms 22104 KB Output is correct
30 Correct 4 ms 22108 KB Output is correct
31 Correct 7 ms 22108 KB Output is correct
32 Correct 6 ms 22108 KB Output is correct
33 Correct 39 ms 22596 KB Output is correct
34 Correct 39 ms 22496 KB Output is correct
35 Correct 55 ms 25172 KB Output is correct
36 Correct 26 ms 23344 KB Output is correct
37 Correct 114 ms 26680 KB Output is correct
38 Correct 109 ms 26156 KB Output is correct
39 Correct 113 ms 26432 KB Output is correct
40 Correct 127 ms 26308 KB Output is correct
41 Correct 108 ms 26140 KB Output is correct
42 Correct 94 ms 23644 KB Output is correct
43 Correct 86 ms 23664 KB Output is correct
44 Correct 163 ms 56020 KB Output is correct
45 Correct 92 ms 26196 KB Output is correct
46 Correct 96 ms 24124 KB Output is correct
47 Correct 141 ms 45160 KB Output is correct
48 Correct 11 ms 44380 KB Output is correct
49 Correct 13 ms 44584 KB Output is correct
50 Correct 9 ms 44380 KB Output is correct
51 Correct 50 ms 45528 KB Output is correct
52 Correct 57 ms 45528 KB Output is correct
53 Correct 20 ms 44892 KB Output is correct
54 Correct 6 ms 43712 KB Output is correct
55 Correct 7 ms 43740 KB Output is correct
56 Correct 13 ms 44892 KB Output is correct
57 Correct 57 ms 43860 KB Output is correct
58 Correct 12 ms 44124 KB Output is correct
59 Correct 15 ms 44456 KB Output is correct
60 Correct 19 ms 44380 KB Output is correct
61 Correct 16 ms 44380 KB Output is correct
62 Correct 47 ms 45148 KB Output is correct
63 Correct 317 ms 46552 KB Output is correct
64 Correct 528 ms 46424 KB Output is correct
65 Correct 981 ms 46588 KB Output is correct
66 Correct 820 ms 45016 KB Output is correct
67 Correct 866 ms 45008 KB Output is correct