oj.uz

Submission #735938

# Submission time Handle Problem Language Result Execution time Memory
735938 2023-05-05T04:05:48 Z Cutebol Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 458 ms 96788 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define Ganyu ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define endl "\n"
#define ff first
#define ss second
  
const int N = 3e4 + 5 ;
const int inf = 1e9 ;
const int mod = 1e9 + 7 ;

int n , m , ans = inf ;
int p[N] , d[N] ;
int edge[2005][2005] ;
vector <pair <int , int> > g[N] ;

void djikstra( int s ){
	
	set <pair <int , int> > q ;
	q.insert({0,s}) ;
	d[s] = 0 ; 
	while ( !q.empty() ){
		int v = q.begin()->ss ;
		q.erase(q.begin()) ;
		for ( auto to : g[v] ){
			if ( d[to.ff] > d[v]+to.ss ){
				q.erase({d[to.ff],to.ff}) ;
				d[to.ff] = d[v]+to.ss ;
				q.insert({d[to.ff],to.ff}) ;
			}
		}
	}
	
}

void solve(){
	int a , b ;
	cin >> n >> m ;
	for ( int i = 0 ; i < n ; i ++ ) for ( int j = 0 ; j < n ; j ++ ) edge[i][j] = inf ;
	for ( int i = 0 ; i < n ; i ++ ) d[i] = inf ;
	for ( int i = 0 ; i < m ; i ++ ) {
		int x , y ;
		cin >> x >> p[x] ;
		if (!i) a = x ;
		if(i==1) b = x ;
		for ( int j = x + p[x] ; j < n ; j += p[x] ) edge[x][j] = min ( edge[x][j] , (j-x)/p[x] ) ;
		for ( int j = x - p[x] ; j >= 0 ; j -= p[x] ) edge[x][j] = min ( edge[x][j] , (x-j)/p[x] ) ;
	}
	for ( int i = 0 ; i < n ; i ++ )
		for ( int j = 0 ; j < n ; j ++ )
			if (edge[i][j]!= inf) g[i].push_back({j,edge[i][j]}) ;
	djikstra(a) ;
	if ( d[b] == inf ) cout << -1 ;
	else cout << d[b] ;
}
signed main(){
//	fopn("") ;
//	Ganyu ;
	int t = 1 ;
//	cin >> t ;
	while ( t -- ) solve() ;
	
}

Compilation message

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:50:11: warning: unused variable 'y' [-Wunused-variable]
   50 |   int x , y ;
      |           ^
skyscraper.cpp: In function 'void fopn(std::string)':
skyscraper.cpp:8:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:8:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:60:10: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |  djikstra(a) ;
      |  ~~~~~~~~^~~
skyscraper.cpp:61:10: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |  if ( d[b] == inf ) cout << -1 ;
      |       ~~~^

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 1016 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 1144 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 2 ms 1620 KB Output is correct
12 Correct 3 ms 1492 KB Output is correct
13 Correct 3 ms 1620 KB Output is correct
14 Correct 2 ms 1492 KB Output is correct
15 Correct 2 ms 1492 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1012 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 1016 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 2 ms 1620 KB Output is correct
12 Correct 3 ms 1492 KB Output is correct
13 Correct 3 ms 1620 KB Output is correct
14 Correct 2 ms 1536 KB Output is correct
15 Correct 2 ms 1492 KB Output is correct
16 Correct 2 ms 2260 KB Output is correct
17 Correct 6 ms 8788 KB Output is correct
18 Correct 19 ms 28504 KB Output is correct
19 Correct 18 ms 32468 KB Output is correct
20 Correct 111 ms 96704 KB Output is correct
21 Correct 2 ms 3796 KB Output is correct
22 Correct 18 ms 29024 KB Output is correct
23 Correct 17 ms 26268 KB Output is correct
24 Correct 21 ms 31212 KB Output is correct
25 Correct 23 ms 32632 KB Output is correct
26 Correct 43 ms 32696 KB Output is correct
27 Correct 40 ms 32576 KB Output is correct
28 Correct 21 ms 32852 KB Output is correct
29 Correct 24 ms 33156 KB Output is correct
30 Correct 21 ms 32852 KB Output is correct
31 Correct 21 ms 33056 KB Output is correct
32 Correct 23 ms 32888 KB Output is correct
33 Correct 26 ms 33452 KB Output is correct
34 Correct 23 ms 33484 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 2 ms 1620 KB Output is correct
12 Correct 3 ms 1492 KB Output is correct
13 Correct 3 ms 1620 KB Output is correct
14 Correct 2 ms 1492 KB Output is correct
15 Correct 2 ms 1536 KB Output is correct
16 Correct 2 ms 2260 KB Output is correct
17 Correct 7 ms 8788 KB Output is correct
18 Correct 20 ms 28500 KB Output is correct
19 Correct 23 ms 32444 KB Output is correct
20 Correct 118 ms 96588 KB Output is correct
21 Correct 3 ms 3796 KB Output is correct
22 Correct 18 ms 29012 KB Output is correct
23 Correct 16 ms 26196 KB Output is correct
24 Correct 21 ms 31128 KB Output is correct
25 Correct 22 ms 32668 KB Output is correct
26 Correct 46 ms 32648 KB Output is correct
27 Correct 41 ms 32564 KB Output is correct
28 Correct 21 ms 32852 KB Output is correct
29 Correct 23 ms 33120 KB Output is correct
30 Correct 21 ms 32832 KB Output is correct
31 Correct 22 ms 32980 KB Output is correct
32 Correct 22 ms 32844 KB Output is correct
33 Correct 23 ms 33496 KB Output is correct
34 Correct 27 ms 33492 KB Output is correct
35 Correct 28 ms 25812 KB Output is correct
36 Correct 11 ms 15060 KB Output is correct
37 Correct 37 ms 37248 KB Output is correct
38 Correct 40 ms 37124 KB Output is correct
39 Correct 42 ms 37476 KB Output is correct
40 Correct 42 ms 37200 KB Output is correct
41 Correct 41 ms 36952 KB Output is correct
42 Correct 381 ms 32896 KB Output is correct
43 Correct 380 ms 32752 KB Output is correct
44 Correct 446 ms 96788 KB Output is correct
45 Correct 37 ms 36812 KB Output is correct
46 Correct 44 ms 36856 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1016 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 1016 KB Output is correct
4 Correct 1 ms 1012 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 2 ms 1540 KB Output is correct
12 Correct 3 ms 1492 KB Output is correct
13 Correct 3 ms 1620 KB Output is correct
14 Correct 2 ms 1492 KB Output is correct
15 Correct 2 ms 1492 KB Output is correct
16 Correct 2 ms 2260 KB Output is correct
17 Correct 7 ms 8788 KB Output is correct
18 Correct 16 ms 28600 KB Output is correct
19 Correct 18 ms 32468 KB Output is correct
20 Correct 109 ms 96716 KB Output is correct
21 Correct 2 ms 3796 KB Output is correct
22 Correct 17 ms 29112 KB Output is correct
23 Correct 16 ms 26196 KB Output is correct
24 Correct 24 ms 31180 KB Output is correct
25 Correct 22 ms 32596 KB Output is correct
26 Correct 42 ms 32700 KB Output is correct
27 Correct 40 ms 32568 KB Output is correct
28 Correct 21 ms 32820 KB Output is correct
29 Correct 24 ms 33116 KB Output is correct
30 Correct 20 ms 32784 KB Output is correct
31 Correct 23 ms 33056 KB Output is correct
32 Correct 22 ms 32852 KB Output is correct
33 Correct 23 ms 33492 KB Output is correct
34 Correct 23 ms 33508 KB Output is correct
35 Correct 34 ms 25848 KB Output is correct
36 Correct 11 ms 15060 KB Output is correct
37 Correct 37 ms 37244 KB Output is correct
38 Correct 41 ms 37116 KB Output is correct
39 Correct 42 ms 37428 KB Output is correct
40 Correct 43 ms 37196 KB Output is correct
41 Correct 44 ms 37020 KB Output is correct
42 Correct 379 ms 32784 KB Output is correct
43 Correct 376 ms 32780 KB Output is correct
44 Correct 458 ms 96784 KB Output is correct
45 Correct 38 ms 36864 KB Output is correct
46 Correct 38 ms 36856 KB Output is correct
47 Runtime error 60 ms 66704 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -