답안 #960688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
960688	2024-04-10T23:17:21 Z	_rain_	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	6 ms	16016 KB

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
{
	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[0]] = 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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	15964 KB	Output is correct
2	Correct	6 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	4 ms	15964 KB	Output is correct
6	Correct	3 ms	15964 KB	Output is correct
7	Correct	3 ms	15960 KB	Output is correct

Subtask #2

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	15960 KB	Output is correct
2	Correct	2 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	15964 KB	Output is correct
6	Correct	2 ms	15964 KB	Output is correct
7	Correct	3 ms	15964 KB	Output is correct
8	Incorrect	3 ms	15964 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #3

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	15964 KB	Output is correct
2	Correct	4 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	15964 KB	Output is correct
6	Correct	3 ms	15964 KB	Output is correct
7	Correct	3 ms	15964 KB	Output is correct
8	Incorrect	4 ms	16000 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #4

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	15964 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	15964 KB	Output is correct
5	Correct	3 ms	15964 KB	Output is correct
6	Correct	3 ms	15960 KB	Output is correct
7	Correct	3 ms	15960 KB	Output is correct
8	Incorrect	3 ms	15964 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #5

0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	15964 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	15964 KB	Output is correct
6	Correct	4 ms	15964 KB	Output is correct
7	Correct	3 ms	16016 KB	Output is correct
8	Incorrect	3 ms	15964 KB	Output isn't correct
9	Halted	0 ms	0 KB	-