Submission #961134

#	Time	Username	Problem	Language	Result	Execution time	Memory
961134		_rain_	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	981 ms	56020 KiB

skyscraper

/** 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 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43