답안 #960689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
960689	2024-04-10T23:19:25 Z	_rain_	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	185 ms	48568 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[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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #960689

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
14.0 / 14.0

Subtask #4
0 / 21.0

Subtask #5
0 / 43.0