oj.uz

Submission #535917

# Submission time Handle Problem Language Result Execution time Memory
535917 2022-03-11T20:18:52 Z PoPularPlusPlus Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 52 ms 468 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);

void solve(){
	int n , m;
	cin >> n >> m;
	int rt = sqrt(n);
	vector<pair<int,int>> adj[n + 1][rt+1];
	vector<int> v[n];
	int s , e;
	for(int i = 0; i < m; i++){
		int b , p;
		cin >> b >> p;
		if(i == 0)s = b;
		if(i == 1)e = b;
		v[b].pb(p);
		if(p > rt){
			int pos = b , dis = 0;
			while(pos - p >= 0){
				pos -= p;
				dis++;
				adj[pos][0].pb(mp(pos , dis));
			}
			pos = b;
			dis = 0;
			while(pos + p < n){
				pos += p;
				dis++;
				adj[pos][0].pb(mp(pos , dis));
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 1; j <= rt; j++){
			if(i - j >= 0){
				adj[i][j].pb(mp(i-j , 1));
			}
			if(i + j < n){
				adj[i][j].pb(mp(i+j , 1));
			}
		}
	}
	int dis[n][rt+1];
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= rt; j++){
			dis[i][j] = 1e9;
		}
	}
	priority_queue< pair<int,pair<int,int>> , vector<pair<int,pair<int,int>>> , greater<pair<int,pair<int,int>>> > pq;
	dis[s][0] = 0;
	pq.push(mp(0 , mp(s , 0)));
	while(pq.size()){
		int di = pq.top().vf , pos = pq.top().vs.vf , pow = pq.top().vs.vs;
		//cout << di << ' ' << pos << ' ' << pow << '\n';
		pq.pop();
		if(dis[pos][pow] < di)continue;
		if(pow == 0){
			for(int i : v[pos]){
				pq.push(mp(di , mp(pos , i)));
			}
		}
		for(auto i : adj[pos][pow]){
			if(dis[i.vf][pow] > di + i.vs){
				dis[i.vf][pow] = di + i.vs;
				if(pow != 0 && dis[i.vf][0] > di + i.vs){
					dis[i.vf][0] = di + i.vs;
					pq.push(mp(di + i.vs,mp(i.vf , 0)));
				}
				pq.push(mp(di + i.vs , mp(i.vf , pow)));
			}
		}
	}
	cout << (dis[e][0] == 1e9 ? -1 : dis[e][0]) << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

Compilation message

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:67:12: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |  dis[s][0] = 0;
      |  ~~~~~~~~~~^~~
skyscraper.cpp:90:19: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |  cout << (dis[e][0] == 1e9 ? -1 : dis[e][0]) << '\n';
      |           ~~~~~~~~^

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Runtime error 34 ms 340 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Runtime error 52 ms 444 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Runtime error 38 ms 468 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Runtime error 36 ms 340 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -