oj.uz

Submission #514460

# Submission time Handle Problem Language Result Execution time Memory
514460 2022-01-18T08:03:21 Z thehidden Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 2 ms 2432 KB 
#include<bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
#define LL long long
#define UL unsigned long long
#define BASE 1000000000000000000ull
#define ii pair < int , int >
#define iii pair < int , ii >
#define iv pair < ii , ii >
#define vi vector <int> 
#define vii vector <vi>
#define vp vector <ii>
#define vpp vector <vp>

#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)
#define REP(i , n) for(int i = 0 ; i < n ; ++i)
#define FORD(i , n , x) for(int i = n ; i >= x ; --i)
#define FORC(v , a) for(auto v : a)

#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define lovethi ios::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
#define fill_a(x , i) memset(x , i ,sizeof x) ;
#define ar array
const int oo = 1e9 + 7 ;
const int N = 3e4 + 5 ;
const int MOD = 1e9 + 7 ;

int n, m;
map <int, int> dp[N];
vector <int> a[N];
void bfs() {

	REP(i, n) REP(j, n) dp[i][j] = oo;
 	priority_queue <iii, vector <iii>, greater <iii>> pq;

	FORC(v, a[0]) pq.push(iii(0, ii(0, v))), dp[0][v] = 0;

	while(pq.size()) {
		int u = pq.top().se.fi, nxt = pq.top().se.se, cost = pq.top().fi;
		pq.pop();
		if(dp[u][nxt] < cost) continue;
		if(u + nxt < n && dp[u + nxt][nxt] > dp[u][nxt] + 1) {
			dp[u + nxt][nxt] = dp[u][nxt] + 1;
		 	pq.push(iii(dp[u + nxt][nxt], ii(u + nxt, nxt)));
		}
		if(u - nxt >= 0 && dp[u - nxt][nxt] > dp[u][nxt] + 1) {
			dp[u - nxt][nxt] = dp[u][nxt] + 1;
		 	pq.push(iii(dp[u - nxt][nxt], ii(u - nxt, nxt)));
		}
		FORC(v, a[u]) {
		 	if(u + v < n && dp[u + v][v] > dp[u][nxt] + 1) {
		 		dp[u + v][v] = dp[u][nxt] + 1;
		 		pq.push(iii(dp[u + v][v], ii(u + v, v)));
		 	}
		 	if(u - v >= 0 && dp[u - v][v] > dp[u][nxt] + 1) {
		 		dp[u - v][v] = dp[u][nxt] + 1;
		 		pq.push(iii(dp[u - v][v], ii(u - v, v)));
		 	}
		 }
	}
	set <int> res;
	REP(i, n) {
		if(dp[1][i] != oo) res.insert(dp[1][i]);
	}
	if(res.size()) {
		cout << *res.begin();
		return;
	} cout << -1;
}
signed main() {
  	lovethi    
     cin >> n >> m;          

    	FOR(i, 1, m) {
    		int u, v;
    		cin >> u >> v;
    		a[u].pb(v);
    	}
    	bfs();
}

                                                                                                                                                             
/*
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▄▀▀▀▀▄▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒█▒▒▒▒▀▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒█▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▀▄▄▄▄▀▒▒▒▒▒▒▒▒
▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██▌░░▒▒▒▒▒▒▒▒▒▒▒▄▄▄▄▄▒▒▒▒▒▒▒▒▒
▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄███▀░░░░▒▒▒▒▒▒▒▒▒▒█▒▒▒▒█▒▒▒▒▒▒▒▒
▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░▄█░░░░▒▒▒▒▒▒▒▒▒█▒▒▒▒█▒▒▒▒▒▒▒▒
▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░▄████████▀░░░░▒▒▒▒▒▒▒▒▒█▀▀▀▀▒▒▒▒▒▒▒▒▒
▒▒░░░░░░░░░░░░░░░░░░░░░░░░▄█████████░░░░░░░▒▒▒▒▒▒▒▒█▒▒▒▒▒▒▒▒▒▒▒▒▒
▒░░░░░░░░░░░░░░░░░░░░░░░░░░▄███████▌░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒░░░░░░░░░░░░░░░░░░░░░░░░▄█████████░░░░░░░░▒▒▒▒▒▒▒▒█▀▒▒▒█▒▒▒▒▒▒▒▒
▒░░░░░░░░░░░░░░░░░░░░░▄███████████▌░░░░░░░░▒▒▒▒▒▒▒▒█▒█▒▒█▒▒▒▒▒▒▒▒
▒░░░░░░░░░░░░░░░▄▄▄▄██████████████▌░░░░░░░░▒▒▒▒▒▒▒▒█▒▒█▒█▒▒▒▒▒▒▒▒
▒░░░░░░░░░░░▄▄███████████████████▌░░░░░░░░░▒▒▒▒▒▒▒▒█▒▒▒▄█▒▒▒▒▒▒▒▒
▒░░░░░░░░░▄██████████████████████▌░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒░░░░░░░░████████████████████████░░░░░░░░░░▒▒▒▒▒▒▒▒█▀▀▀▀▄▒▒▒▒▒▒▒▒
▒█░░░░░▐██████████▌░▀▀███████████░░░░░░░░░░▒▒▒▒▒▒▒▒█▄▄▄▄▀▒▒▒▒▒▒▒▒
▐██░░░▄██████████▌░░░░░░░░░▀██▐█▌░░░░░░░░░▒▒▒▒▒▒▒▒▒█▒▒▒▒█▒▒▒▒▒▒▒▒
▒██████░█████████ ░░░░░░░░░░▐█▐█▌░░░░░░░░░▒▒▒▒▒▒▒▒▒█▄▄▄▄▀▒▒▒▒▒▒▒▒
▒▒▀▀▀▀░░░██████▀░░░░░░░░░░░░▐█▐█▌░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒░░░░▐█████▌░░░░░░░░░░░░▐█▐█▌░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒░░░░███▀██░░░░░░░░░░░░░█░█▌░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒░▐██░░░██░░░░░░░░▄▄████████▄▄▄▄▄▄▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒██▌░░░░█▄░░░░░░▄███████████████████▄▄▄▄▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▐██▒▒░░░██▄▄████████████████████████████████████████████
▒▒▒▒▒▒▒▒▒▒▐██▒▒▄█████████████████████████████████████████████████
▒▒▒▒▒▒▒▒▒▒▄▄█████████████████████████████████████████████████████
█████████████████████████████████████████████████████████████████
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2380 KB Output is correct
2 Correct 1 ms 2380 KB Output is correct
3 Incorrect 1 ms 2432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2380 KB Output is correct
2 Correct 1 ms 2380 KB Output is correct
3 Incorrect 1 ms 2380 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2424 KB Output is correct
2 Correct 1 ms 2424 KB Output is correct
3 Incorrect 2 ms 2432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2424 KB Output is correct
2 Correct 1 ms 2424 KB Output is correct
3 Incorrect 1 ms 2380 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2428 KB Output is correct
2 Correct 2 ms 2380 KB Output is correct
3 Incorrect 1 ms 2380 KB Output isn't correct
4 Halted 0 ms 0 KB -