oj.uz

Submission #735936

# Submission time Handle Problem Language Result Execution time Memory
735936 2023-05-05T03:59:12 Z Cutebol Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 239 ms 262144 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] ;
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 ++ ) 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] ) g[x].push_back( { j , ( j - x ) / p[x] } ) ;
		for ( int j = x - p[x] ; j >= 0 ; j -= p[x] ) g[x].push_back( { j , ( x - j ) / p[x] } ) ;
	}
	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:48:11: warning: unused variable 'y' [-Wunused-variable]
   48 |   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:56:10: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |  if ( d[b] == inf ) cout << -1 ;
      |       ~~~^
skyscraper.cpp:55:10: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |  djikstra(a) ;
      |  ~~~~~~~~^~~

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 980 KB Output is correct
5 Correct 1 ms 1012 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 1004 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 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 2 ms 1236 KB Output is correct
12 Correct 6 ms 5188 KB Output is correct
13 Correct 6 ms 5232 KB Output is correct
14 Correct 2 ms 1028 KB Output is correct
15 Correct 2 ms 1108 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 1008 KB Output is correct
3 Correct 1 ms 1016 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 1004 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 2 ms 1144 KB Output is correct
12 Correct 7 ms 5220 KB Output is correct
13 Correct 6 ms 5228 KB Output is correct
14 Correct 1 ms 1108 KB Output is correct
15 Correct 2 ms 1024 KB Output is correct
16 Correct 1 ms 1108 KB Output is correct
17 Correct 2 ms 1536 KB Output is correct
18 Correct 1 ms 1108 KB Output is correct
19 Correct 1 ms 1108 KB Output is correct
20 Correct 71 ms 65228 KB Output is correct
21 Correct 1 ms 980 KB Output is correct
22 Correct 1 ms 1108 KB Output is correct
23 Correct 2 ms 1108 KB Output is correct
24 Correct 3 ms 1276 KB Output is correct
25 Correct 3 ms 1236 KB Output is correct
26 Correct 86 ms 66960 KB Output is correct
27 Correct 84 ms 66852 KB Output is correct
28 Correct 2 ms 1404 KB Output is correct
29 Correct 5 ms 2388 KB Output is correct
30 Correct 2 ms 1492 KB Output is correct
31 Correct 3 ms 1748 KB Output is correct
32 Correct 2 ms 1492 KB Output is correct
33 Correct 7 ms 3592 KB Output is correct
34 Correct 7 ms 3536 KB Output is correct

Subtask #4
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 1012 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 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 2 ms 1148 KB Output is correct
12 Correct 7 ms 5188 KB Output is correct
13 Correct 7 ms 5232 KB Output is correct
14 Correct 2 ms 1020 KB Output is correct
15 Correct 2 ms 1108 KB Output is correct
16 Correct 1 ms 1140 KB Output is correct
17 Correct 3 ms 1492 KB Output is correct
18 Correct 1 ms 1108 KB Output is correct
19 Correct 1 ms 1108 KB Output is correct
20 Correct 69 ms 65320 KB Output is correct
21 Correct 1 ms 980 KB Output is correct
22 Correct 1 ms 1096 KB Output is correct
23 Correct 2 ms 1108 KB Output is correct
24 Correct 3 ms 1364 KB Output is correct
25 Correct 4 ms 1236 KB Output is correct
26 Correct 88 ms 67000 KB Output is correct
27 Correct 84 ms 66884 KB Output is correct
28 Correct 2 ms 1492 KB Output is correct
29 Correct 6 ms 2388 KB Output is correct
30 Correct 2 ms 1492 KB Output is correct
31 Correct 3 ms 1780 KB Output is correct
32 Correct 3 ms 1492 KB Output is correct
33 Correct 6 ms 3576 KB Output is correct
34 Correct 7 ms 3456 KB Output is correct
35 Correct 16 ms 4148 KB Output is correct
36 Correct 4 ms 1364 KB Output is correct
37 Correct 17 ms 7436 KB Output is correct
38 Correct 21 ms 6116 KB Output is correct
39 Correct 21 ms 6444 KB Output is correct
40 Correct 21 ms 6228 KB Output is correct
41 Correct 21 ms 5972 KB Output is correct
42 Runtime error 233 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1008 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 1016 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 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 2 ms 1240 KB Output is correct
12 Correct 6 ms 5192 KB Output is correct
13 Correct 6 ms 5228 KB Output is correct
14 Correct 2 ms 1108 KB Output is correct
15 Correct 2 ms 1108 KB Output is correct
16 Correct 1 ms 1108 KB Output is correct
17 Correct 3 ms 1492 KB Output is correct
18 Correct 1 ms 1108 KB Output is correct
19 Correct 1 ms 1108 KB Output is correct
20 Correct 72 ms 65240 KB Output is correct
21 Correct 1 ms 980 KB Output is correct
22 Correct 2 ms 1108 KB Output is correct
23 Correct 2 ms 1148 KB Output is correct
24 Correct 3 ms 1364 KB Output is correct
25 Correct 3 ms 1276 KB Output is correct
26 Correct 88 ms 67064 KB Output is correct
27 Correct 85 ms 66820 KB Output is correct
28 Correct 2 ms 1492 KB Output is correct
29 Correct 5 ms 2388 KB Output is correct
30 Correct 2 ms 1492 KB Output is correct
31 Correct 3 ms 1748 KB Output is correct
32 Correct 3 ms 1496 KB Output is correct
33 Correct 7 ms 3668 KB Output is correct
34 Correct 8 ms 3444 KB Output is correct
35 Correct 17 ms 4220 KB Output is correct
36 Correct 4 ms 1364 KB Output is correct
37 Correct 17 ms 7380 KB Output is correct
38 Correct 21 ms 6144 KB Output is correct
39 Correct 21 ms 6508 KB Output is correct
40 Correct 27 ms 6268 KB Output is correct
41 Correct 20 ms 6080 KB Output is correct
42 Runtime error 239 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -