oj.uz

Submission #369634

# Submission time Handle Problem Language Result Execution time Memory
369634 2021-02-22T06:41:01 Z Bill_00 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 984 ms 26720 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pp push
#define MOD 1000000007
#define INF 1e18
#define N 30005
#define M 5000000
const int c=174;
typedef long long ll;
using namespace std;
int b[N],p[N],pos[N],path[N];
bool vis[N];
set<int>v[c][c];
int main(){
	// ios_base::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0)
	memset(pos,-1,sizeof(pos));
	memset(path,-1,sizeof(path));
 	int n,m;
 	cin >> n >> m;
 	for(int i=0;i<m;i++){
 		cin >> b[i] >> p[i];
 		pos[b[i]]=i;
 		for(int j=1;j<c;j++){
 			v[j][b[i]%j].insert(i);
 		}
 	}
 	priority_queue<pair<int,int> >pq;
 	pq.push({0,0});
 	while(!pq.empty()){
 		int cost=-pq.top().ff;
 		int doge_id=pq.top().ss;
 		path[doge_id]=cost;
 		pq.pop();
 		vis[doge_id]=1;
 		if(p[doge_id]>=c){
 			for(int i=b[doge_id]%p[doge_id];i<n;i+=p[doge_id]){
 				if(pos[i]!=-1){
 					if(vis[pos[i]]==0){
 						pq.push({-(cost+(abs(b[doge_id]-i))/p[doge_id]),pos[i]});
 					}
 				}
 			}
 		}
 		else{
 			for(int i=1;i<c;i++){
 				v[i][b[doge_id]%i].erase(doge_id);
 			}
 			for(auto it=v[p[doge_id]][b[doge_id]%p[doge_id]].begin();it!=v[p[doge_id]][b[doge_id]%p[doge_id]].end();++it){
 				if(vis[*it]==0){
 					pq.push({-(cost+(abs(b[*it]-b[doge_id]))/p[doge_id]),*it});
 				}
 			}
 		}
 		while(!pq.empty() && vis[pq.top().ss]==1) pq.pop();
 	}
 	cout << path[1];
 
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2176 KB Output is correct
2 Correct 2 ms 2028 KB Output is correct
3 Correct 2 ms 2176 KB Output is correct
4 Correct 2 ms 2048 KB Output is correct
5 Correct 2 ms 2028 KB Output is correct
6 Correct 2 ms 2028 KB Output is correct
7 Correct 2 ms 2028 KB Output is correct
8 Correct 2 ms 2156 KB Output is correct
9 Correct 3 ms 2412 KB Output is correct
10 Correct 17 ms 5228 KB Output is correct
11 Correct 170 ms 19612 KB Output is correct
12 Correct 672 ms 26584 KB Output is correct
13 Correct 717 ms 26592 KB Output is correct
14 Correct 121 ms 18548 KB Output is correct
15 Correct 114 ms 18540 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2048 KB Output is correct
2 Correct 2 ms 2028 KB Output is correct
3 Correct 2 ms 2028 KB Output is correct
4 Correct 2 ms 2028 KB Output is correct
5 Correct 2 ms 2028 KB Output is correct
6 Correct 2 ms 2028 KB Output is correct
7 Correct 2 ms 2028 KB Output is correct
8 Correct 2 ms 2156 KB Output is correct
9 Correct 3 ms 2432 KB Output is correct
10 Correct 19 ms 5228 KB Output is correct
11 Correct 159 ms 19464 KB Output is correct
12 Correct 681 ms 26580 KB Output is correct
13 Correct 723 ms 26592 KB Output is correct
14 Correct 115 ms 18540 KB Output is correct
15 Correct 118 ms 18540 KB Output is correct
16 Correct 34 ms 8812 KB Output is correct
17 Correct 185 ms 16836 KB Output is correct
18 Correct 54 ms 10092 KB Output is correct
19 Correct 21 ms 6508 KB Output is correct
20 Correct 943 ms 26592 KB Output is correct
21 Correct 68 ms 11500 KB Output is correct
22 Correct 32 ms 7788 KB Output is correct
23 Incorrect 60 ms 9836 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2028 KB Output is correct
2 Correct 2 ms 2028 KB Output is correct
3 Correct 2 ms 2028 KB Output is correct
4 Correct 2 ms 2028 KB Output is correct
5 Correct 2 ms 2028 KB Output is correct
6 Correct 2 ms 2028 KB Output is correct
7 Correct 2 ms 2048 KB Output is correct
8 Correct 2 ms 2156 KB Output is correct
9 Correct 3 ms 2412 KB Output is correct
10 Correct 16 ms 5228 KB Output is correct
11 Correct 157 ms 19464 KB Output is correct
12 Correct 706 ms 26580 KB Output is correct
13 Correct 693 ms 26612 KB Output is correct
14 Correct 116 ms 18540 KB Output is correct
15 Correct 117 ms 18540 KB Output is correct
16 Correct 35 ms 8812 KB Output is correct
17 Correct 200 ms 16876 KB Output is correct
18 Correct 54 ms 10092 KB Output is correct
19 Correct 20 ms 6508 KB Output is correct
20 Correct 927 ms 26592 KB Output is correct
21 Correct 67 ms 11628 KB Output is correct
22 Correct 30 ms 7788 KB Output is correct
23 Incorrect 53 ms 9836 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2028 KB Output is correct
2 Correct 2 ms 2028 KB Output is correct
3 Correct 2 ms 2156 KB Output is correct
4 Correct 2 ms 2028 KB Output is correct
5 Correct 2 ms 2028 KB Output is correct
6 Correct 2 ms 2172 KB Output is correct
7 Correct 2 ms 2028 KB Output is correct
8 Correct 2 ms 2176 KB Output is correct
9 Correct 3 ms 2412 KB Output is correct
10 Correct 16 ms 5228 KB Output is correct
11 Correct 170 ms 19432 KB Output is correct
12 Correct 687 ms 26580 KB Output is correct
13 Correct 711 ms 26596 KB Output is correct
14 Correct 136 ms 18540 KB Output is correct
15 Correct 117 ms 18540 KB Output is correct
16 Correct 37 ms 8812 KB Output is correct
17 Correct 190 ms 16900 KB Output is correct
18 Correct 50 ms 10092 KB Output is correct
19 Correct 21 ms 6508 KB Output is correct
20 Correct 984 ms 26720 KB Output is correct
21 Correct 70 ms 11628 KB Output is correct
22 Correct 43 ms 8064 KB Output is correct
23 Incorrect 53 ms 9836 KB Output isn't correct
24 Halted 0 ms 0 KB -