oj.uz

Submission #228917

# Submission time Handle Problem Language Result Execution time Memory
228917 2020-05-03T05:44:53 Z alishahali1382 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 642 ms 262148 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int SQ=180, MAXN=180*30000;

int n, m, k, u, v, x, y, t, a, b, ans;
int B[MAXN], P[MAXN];
int dist[MAXN];
bool mark[MAXN];
vector<pii> G[MAXN];
priority_queue<pii, vector<pii>, greater<pii>> pq;

inline void addedge(int v1, int j1, int v2, int j2, int w){
	G[v1*SQ+j1].pb({v2*SQ+j2, w});
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	memset(dist, 63, sizeof(dist));
	cin>>n>>m;
	for (int i=0; i<n; i++) for (int j=1; j<SQ; j++){
		if (i>=j) addedge(i, j, i-j, j, 1);
		if (i+j<n) addedge(i, j, i+j, j, 1);
		addedge(i, j, i, 0, 0);
	}
	for (int i=0; i<m; i++){
		cin>>B[i]>>P[i];
		if (P[i]<SQ) G[B[i]*SQ].pb({B[i]*SQ+P[i], 0});
		else{
			for (int j=1; B[i]-j*P[i]>=0; j++) addedge(B[i], 0, B[i]-P[i]*j, 0, j);
			for (int j=1; B[i]+j*P[i]<n; j++) addedge(B[i], 0, B[i]+P[i]*j, 0, j);
		}
	}
	
	pq.push({dist[B[0]*SQ]=0, B[0]*SQ});
	while (pq.size()){
		int v=pq.top().second;
		pq.pop();
		if (mark[v]) continue ;
		mark[v]=1;
		for (pii p:G[v]) if (dist[p.first]>dist[v]+p.second)
			pq.push({dist[p.first]=dist[v]+p.second, p.first});
	
	}
	
	ans=dist[SQ*B[1]];
	if (ans>=inf) ans=-1;
	cout<<ans<<'\n';
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 148344 KB Output is correct
2 Correct 84 ms 148344 KB Output is correct
3 Correct 83 ms 148344 KB Output is correct
4 Correct 82 ms 148344 KB Output is correct
5 Correct 84 ms 148344 KB Output is correct
6 Correct 83 ms 148364 KB Output is correct
7 Correct 87 ms 148472 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 148344 KB Output is correct
2 Correct 82 ms 148344 KB Output is correct
3 Correct 84 ms 148344 KB Output is correct
4 Correct 89 ms 148376 KB Output is correct
5 Correct 84 ms 148344 KB Output is correct
6 Correct 82 ms 148344 KB Output is correct
7 Correct 83 ms 148344 KB Output is correct
8 Correct 82 ms 148472 KB Output is correct
9 Correct 84 ms 148728 KB Output is correct
10 Correct 84 ms 148984 KB Output is correct
11 Correct 87 ms 149008 KB Output is correct
12 Correct 85 ms 148984 KB Output is correct
13 Correct 84 ms 148984 KB Output is correct
14 Correct 89 ms 149112 KB Output is correct
15 Correct 86 ms 148960 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 148344 KB Output is correct
2 Correct 92 ms 148344 KB Output is correct
3 Correct 82 ms 148344 KB Output is correct
4 Correct 91 ms 148344 KB Output is correct
5 Correct 83 ms 148344 KB Output is correct
6 Correct 84 ms 148344 KB Output is correct
7 Correct 94 ms 148344 KB Output is correct
8 Correct 87 ms 148496 KB Output is correct
9 Correct 89 ms 148600 KB Output is correct
10 Correct 91 ms 149016 KB Output is correct
11 Correct 85 ms 148984 KB Output is correct
12 Correct 90 ms 148960 KB Output is correct
13 Correct 89 ms 149020 KB Output is correct
14 Correct 89 ms 149068 KB Output is correct
15 Correct 93 ms 148960 KB Output is correct
16 Correct 94 ms 149600 KB Output is correct
17 Correct 126 ms 154208 KB Output is correct
18 Correct 131 ms 162552 KB Output is correct
19 Correct 159 ms 164728 KB Output is correct
20 Correct 143 ms 165112 KB Output is correct
21 Correct 99 ms 151160 KB Output is correct
22 Correct 136 ms 162884 KB Output is correct
23 Correct 150 ms 161532 KB Output is correct
24 Correct 143 ms 164160 KB Output is correct
25 Correct 162 ms 165072 KB Output is correct
26 Correct 134 ms 164988 KB Output is correct
27 Correct 144 ms 165088 KB Output is correct
28 Correct 157 ms 165088 KB Output is correct
29 Correct 162 ms 164984 KB Output is correct
30 Correct 140 ms 164984 KB Output is correct
31 Correct 146 ms 164984 KB Output is correct
32 Correct 175 ms 164920 KB Output is correct
33 Correct 179 ms 165052 KB Output is correct
34 Correct 165 ms 164984 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 148332 KB Output is correct
2 Correct 85 ms 148320 KB Output is correct
3 Correct 85 ms 148344 KB Output is correct
4 Correct 83 ms 148344 KB Output is correct
5 Correct 85 ms 148320 KB Output is correct
6 Correct 86 ms 148472 KB Output is correct
7 Correct 80 ms 148344 KB Output is correct
8 Correct 81 ms 148472 KB Output is correct
9 Correct 87 ms 148656 KB Output is correct
10 Correct 85 ms 148984 KB Output is correct
11 Correct 99 ms 149000 KB Output is correct
12 Correct 85 ms 149112 KB Output is correct
13 Correct 85 ms 149028 KB Output is correct
14 Correct 96 ms 149112 KB Output is correct
15 Correct 86 ms 148984 KB Output is correct
16 Correct 91 ms 149540 KB Output is correct
17 Correct 109 ms 154336 KB Output is correct
18 Correct 145 ms 162528 KB Output is correct
19 Correct 159 ms 164672 KB Output is correct
20 Correct 147 ms 165068 KB Output is correct
21 Correct 94 ms 151136 KB Output is correct
22 Correct 125 ms 162808 KB Output is correct
23 Correct 131 ms 161504 KB Output is correct
24 Correct 143 ms 164216 KB Output is correct
25 Correct 165 ms 165040 KB Output is correct
26 Correct 144 ms 165076 KB Output is correct
27 Correct 140 ms 165116 KB Output is correct
28 Correct 153 ms 165052 KB Output is correct
29 Correct 149 ms 164984 KB Output is correct
30 Correct 147 ms 164988 KB Output is correct
31 Correct 141 ms 165112 KB Output is correct
32 Correct 140 ms 164984 KB Output is correct
33 Correct 167 ms 165012 KB Output is correct
34 Correct 172 ms 165108 KB Output is correct
35 Correct 151 ms 161016 KB Output is correct
36 Correct 116 ms 157280 KB Output is correct
37 Correct 190 ms 165496 KB Output is correct
38 Correct 183 ms 166136 KB Output is correct
39 Correct 196 ms 166264 KB Output is correct
40 Correct 180 ms 166320 KB Output is correct
41 Correct 189 ms 166264 KB Output is correct
42 Correct 150 ms 165748 KB Output is correct
43 Correct 147 ms 165728 KB Output is correct
44 Correct 138 ms 165748 KB Output is correct
45 Correct 211 ms 167416 KB Output is correct
46 Correct 217 ms 167412 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 148344 KB Output is correct
2 Correct 92 ms 148364 KB Output is correct
3 Correct 86 ms 148344 KB Output is correct
4 Correct 86 ms 148496 KB Output is correct
5 Correct 91 ms 148344 KB Output is correct
6 Correct 87 ms 148348 KB Output is correct
7 Correct 80 ms 148344 KB Output is correct
8 Correct 82 ms 148472 KB Output is correct
9 Correct 92 ms 148692 KB Output is correct
10 Correct 97 ms 148984 KB Output is correct
11 Correct 87 ms 148984 KB Output is correct
12 Correct 85 ms 149004 KB Output is correct
13 Correct 88 ms 148984 KB Output is correct
14 Correct 87 ms 148984 KB Output is correct
15 Correct 86 ms 148988 KB Output is correct
16 Correct 97 ms 149624 KB Output is correct
17 Correct 117 ms 154232 KB Output is correct
18 Correct 127 ms 162552 KB Output is correct
19 Correct 137 ms 164704 KB Output is correct
20 Correct 142 ms 165112 KB Output is correct
21 Correct 99 ms 151164 KB Output is correct
22 Correct 128 ms 162736 KB Output is correct
23 Correct 131 ms 161528 KB Output is correct
24 Correct 154 ms 164148 KB Output is correct
25 Correct 146 ms 165112 KB Output is correct
26 Correct 137 ms 164984 KB Output is correct
27 Correct 137 ms 164984 KB Output is correct
28 Correct 148 ms 165156 KB Output is correct
29 Correct 153 ms 164952 KB Output is correct
30 Correct 147 ms 164896 KB Output is correct
31 Correct 153 ms 164984 KB Output is correct
32 Correct 143 ms 164960 KB Output is correct
33 Correct 161 ms 165112 KB Output is correct
34 Correct 168 ms 164996 KB Output is correct
35 Correct 148 ms 161016 KB Output is correct
36 Correct 121 ms 157364 KB Output is correct
37 Correct 179 ms 165496 KB Output is correct
38 Correct 185 ms 166368 KB Output is correct
39 Correct 204 ms 166172 KB Output is correct
40 Correct 205 ms 166136 KB Output is correct
41 Correct 182 ms 166192 KB Output is correct
42 Correct 145 ms 165748 KB Output is correct
43 Correct 153 ms 165748 KB Output is correct
44 Correct 141 ms 165736 KB Output is correct
45 Correct 228 ms 167464 KB Output is correct
46 Correct 212 ms 167388 KB Output is correct
47 Correct 642 ms 258132 KB Output is correct
48 Runtime error 414 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
49 Halted 0 ms 0 KB -