oj.uz

Submission #700721

# Submission time Handle Problem Language Result Execution time Memory
700721 2023-02-19T08:30:39 Z Sanzhar23 Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 81 ms 32588 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long	
#define pb push_back
#define bug cout << "bug" << endl
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pll pair <ll, ll> 
#define pii pair <int, int> 
#define triple pair <pair <ll, ll> , ll>   
#define ull unsigned long long
#define ld long double
#define pinode pair <node*, node*>

const ll INF = 9e18 + 5;
const ll inf = 1e9 + 5;
const ll N = 2e3	 + 5;
const ll shift = 2e6;
const ll mod = 998244353;
const ll mod2 = 1e9 + 9;
const ll M = 1e3 + 5;
const ll LOG = 21;
const ll sp = 263;
const ll sp2 = 9973;
const int block = 100;
const double eps = 1e-10;

ll n, m, b[N], p[N], d[N];
vector <pii> g[N];

int main(){
	speed;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		cin >> b[i] >> p[i];
	}
	for(int i = 0; i < m; i++){
		if(i == 1)
			continue;
		for(int j = 0; j < m; j++){
			if(abs(b[i] - b[j]) % p[i] == 0){
				g[i].pb({j, abs(b[i] - b[j]) / p[i]});
			}
		}
	}
	for(int i = 0; i < m; i++){
		d[i] = INF;
	}
	set <pii> st;
	st.insert({0, 0});
	d[0] = 0;
	while(st.size()){
		ll v = st.begin() -> second, len = st.begin() -> first;
		st.erase(st.begin());
		for(auto to : g[v]){
			if(d[v] + to.S < d[to.F]){
				st.erase({d[to.F], to.F});
				d[to.F] = d[v] + to.S;
				st.insert({d[to.F], to.F});
			}
		}
	}
	if(d[1] == INF)
		d[1] = -1;
	cout << d[1] << endl;	
}
/*	
%I64d6


6 1 3
8 1 2 1 5 4		
		



%I64d
*/

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:57:32: warning: unused variable 'len' [-Wunused-variable]
   57 |   ll v = st.begin() -> second, len = st.begin() -> first;
      |                                ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 372 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 380 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 28 ms 2508 KB Output is correct
12 Correct 81 ms 32276 KB Output is correct
13 Correct 65 ms 32524 KB Output is correct
14 Correct 26 ms 1840 KB Output is correct
15 Correct 24 ms 1864 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 368 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 25 ms 2620 KB Output is correct
12 Correct 64 ms 32328 KB Output is correct
13 Correct 62 ms 32580 KB Output is correct
14 Correct 25 ms 1788 KB Output is correct
15 Correct 26 ms 1828 KB Output is correct
16 Correct 5 ms 640 KB Output is correct
17 Correct 18 ms 1044 KB Output is correct
18 Correct 5 ms 468 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 74 ms 32528 KB Output is correct
21 Correct 8 ms 516 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 6 ms 468 KB Output is correct
24 Correct 21 ms 596 KB Output is correct
25 Correct 24 ms 520 KB Output is correct
26 Correct 58 ms 29536 KB Output is correct
27 Correct 64 ms 30392 KB Output is correct
28 Correct 23 ms 588 KB Output is correct
29 Correct 5 ms 596 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 3 ms 500 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 26 ms 1860 KB Output is correct
34 Correct 23 ms 1780 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 404 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 24 ms 2508 KB Output is correct
12 Correct 62 ms 32304 KB Output is correct
13 Correct 57 ms 32508 KB Output is correct
14 Correct 30 ms 1768 KB Output is correct
15 Correct 24 ms 1876 KB Output is correct
16 Correct 5 ms 596 KB Output is correct
17 Correct 19 ms 1100 KB Output is correct
18 Correct 7 ms 468 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 70 ms 32588 KB Output is correct
21 Correct 8 ms 468 KB Output is correct
22 Correct 4 ms 340 KB Output is correct
23 Correct 7 ms 500 KB Output is correct
24 Correct 22 ms 628 KB Output is correct
25 Correct 23 ms 484 KB Output is correct
26 Correct 72 ms 29576 KB Output is correct
27 Correct 66 ms 30324 KB Output is correct
28 Correct 22 ms 600 KB Output is correct
29 Correct 5 ms 684 KB Output is correct
30 Correct 2 ms 340 KB Output is correct
31 Correct 3 ms 468 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 26 ms 1836 KB Output is correct
34 Correct 30 ms 1892 KB Output is correct
35 Incorrect 6 ms 468 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 428 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 30 ms 2508 KB Output is correct
12 Correct 60 ms 32284 KB Output is correct
13 Correct 66 ms 32492 KB Output is correct
14 Correct 26 ms 1868 KB Output is correct
15 Correct 28 ms 1880 KB Output is correct
16 Correct 6 ms 632 KB Output is correct
17 Correct 26 ms 1100 KB Output is correct
18 Correct 6 ms 464 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 70 ms 32584 KB Output is correct
21 Correct 7 ms 512 KB Output is correct
22 Correct 4 ms 432 KB Output is correct
23 Correct 6 ms 488 KB Output is correct
24 Correct 21 ms 596 KB Output is correct
25 Correct 21 ms 520 KB Output is correct
26 Correct 58 ms 29508 KB Output is correct
27 Correct 57 ms 30400 KB Output is correct
28 Correct 20 ms 588 KB Output is correct
29 Correct 4 ms 596 KB Output is correct
30 Correct 1 ms 376 KB Output is correct
31 Correct 3 ms 504 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 23 ms 1796 KB Output is correct
34 Correct 28 ms 1796 KB Output is correct
35 Incorrect 6 ms 560 KB Output isn't correct
36 Halted 0 ms 0 KB -