oj.uz

Submission #535925

# Submission time Handle Problem Language Result Execution time Memory
535925 2022-03-11T20:37:43 Z PoPularPlusPlus Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 391 ms 262144 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 = 500;
	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;
		if(p <= rt)
			v[b].pb(p);
		if(p > rt){
			int pos = b , dis = 0;
			while(pos - p >= 0){
				pos -= p;
				dis++;
				adj[b][0].pb(mp(pos , dis));
			}
			pos = b;
			dis = 0;
			while(pos + p < n){
				pos += p;
				dis++;
				adj[b][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();
		//cout << pos << ' ' << pow << endl;
		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:8:30: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
    8 | #define mp(a,b) make_pair(a,b)
      |                              ^
skyscraper.cpp:27:6: note: 's' was declared here
   27 |  int s , e;
      |      ^
skyscraper.cpp:92:19: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |  cout << (dis[e][0] == 1e9 ? -1 : dis[e][0]) << '\n';
      |           ~~~~~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 3 ms 1876 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 2 ms 2004 KB Output is correct
14 Correct 3 ms 2004 KB Output is correct
15 Correct 3 ms 2004 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 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 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 340 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 3 ms 1876 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 2 ms 1876 KB Output is correct
14 Correct 3 ms 2004 KB Output is correct
15 Correct 3 ms 2004 KB Output is correct
16 Correct 4 ms 3924 KB Output is correct
17 Correct 34 ms 21632 KB Output is correct
18 Correct 94 ms 51688 KB Output is correct
19 Correct 93 ms 59252 KB Output is correct
20 Correct 92 ms 59076 KB Output is correct
21 Correct 10 ms 9300 KB Output is correct
22 Correct 79 ms 52608 KB Output is correct
23 Correct 76 ms 47248 KB Output is correct
24 Correct 97 ms 56272 KB Output is correct
25 Correct 93 ms 59088 KB Output is correct
26 Correct 91 ms 59172 KB Output is correct
27 Correct 94 ms 59100 KB Output is correct
28 Correct 106 ms 59068 KB Output is correct
29 Correct 106 ms 59072 KB Output is correct
30 Correct 95 ms 59072 KB Output is correct
31 Correct 118 ms 59084 KB Output is correct
32 Correct 103 ms 59108 KB Output is correct
33 Correct 119 ms 59228 KB Output is correct
34 Correct 144 ms 59228 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 772 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 3 ms 1876 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 2 ms 1876 KB Output is correct
14 Correct 3 ms 2004 KB Output is correct
15 Correct 3 ms 2004 KB Output is correct
16 Correct 4 ms 3924 KB Output is correct
17 Correct 41 ms 21708 KB Output is correct
18 Correct 82 ms 51608 KB Output is correct
19 Correct 95 ms 59068 KB Output is correct
20 Correct 98 ms 59096 KB Output is correct
21 Correct 11 ms 9300 KB Output is correct
22 Correct 95 ms 52636 KB Output is correct
23 Correct 85 ms 47328 KB Output is correct
24 Correct 90 ms 56256 KB Output is correct
25 Correct 94 ms 59116 KB Output is correct
26 Correct 93 ms 59072 KB Output is correct
27 Correct 95 ms 59072 KB Output is correct
28 Correct 125 ms 59084 KB Output is correct
29 Correct 116 ms 59084 KB Output is correct
30 Correct 95 ms 59116 KB Output is correct
31 Correct 98 ms 59240 KB Output is correct
32 Correct 100 ms 59092 KB Output is correct
33 Correct 116 ms 59232 KB Output is correct
34 Correct 120 ms 59224 KB Output is correct
35 Correct 97 ms 42908 KB Output is correct
36 Correct 55 ms 32316 KB Output is correct
37 Correct 152 ms 57996 KB Output is correct
38 Correct 139 ms 59852 KB Output is correct
39 Correct 149 ms 59904 KB Output is correct
40 Correct 159 ms 59868 KB Output is correct
41 Correct 140 ms 59924 KB Output is correct
42 Correct 104 ms 59720 KB Output is correct
43 Correct 102 ms 59760 KB Output is correct
44 Correct 100 ms 59708 KB Output is correct
45 Correct 209 ms 60204 KB Output is correct
46 Correct 199 ms 60176 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 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 340 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 3 ms 1876 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 2 ms 1876 KB Output is correct
14 Correct 3 ms 2004 KB Output is correct
15 Correct 3 ms 2004 KB Output is correct
16 Correct 4 ms 3992 KB Output is correct
17 Correct 36 ms 21608 KB Output is correct
18 Correct 104 ms 51696 KB Output is correct
19 Correct 95 ms 59084 KB Output is correct
20 Correct 91 ms 59096 KB Output is correct
21 Correct 10 ms 9300 KB Output is correct
22 Correct 82 ms 52636 KB Output is correct
23 Correct 76 ms 47396 KB Output is correct
24 Correct 100 ms 56152 KB Output is correct
25 Correct 96 ms 59076 KB Output is correct
26 Correct 96 ms 59124 KB Output is correct
27 Correct 100 ms 59184 KB Output is correct
28 Correct 116 ms 59084 KB Output is correct
29 Correct 103 ms 59148 KB Output is correct
30 Correct 95 ms 59032 KB Output is correct
31 Correct 99 ms 59144 KB Output is correct
32 Correct 126 ms 59128 KB Output is correct
33 Correct 118 ms 59216 KB Output is correct
34 Correct 117 ms 59152 KB Output is correct
35 Correct 96 ms 42936 KB Output is correct
36 Correct 50 ms 32392 KB Output is correct
37 Correct 172 ms 58016 KB Output is correct
38 Correct 150 ms 59828 KB Output is correct
39 Correct 152 ms 59948 KB Output is correct
40 Correct 167 ms 59944 KB Output is correct
41 Correct 148 ms 59876 KB Output is correct
42 Correct 101 ms 59720 KB Output is correct
43 Correct 107 ms 59760 KB Output is correct
44 Correct 105 ms 59736 KB Output is correct
45 Correct 187 ms 60204 KB Output is correct
46 Correct 196 ms 60156 KB Output is correct
47 Runtime error 391 ms 262144 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -