oj.uz

답안 #555976

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
555976 2022-05-02T05:28:58 Z MurotY Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 135276 KB 
// author : Murot_06
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ff first
#define ll long long
#define ss second
using namespace std;
const int N=1e6+7, M=1e9+7;
ll a[N];
vector <pair <ll,ll>> g[N];
set <ll> v[N];
void solve()
{
	int n, m;
	cin >> n >> m;
	for (int i=1;i<=m;i++){
		ll x, y;
		cin >> x >> y;
		a[i]=x;
		v[x].insert(y);
	}
	for (int i=0;i<n;i++){
		for (auto l:v[i]){
			for (int j=i+l;j<n;j+=l){
				g[i].push_back({j, (j-i)/l});
			//	if (v[j].count(l)) break;
			}
			for (int j=i-l;j>=0;j-=l){
				g[i].push_back({j, (i-j)/l});
			//	if (v[j].count(l)) break;
			}
		}
	}
//	priority_queue<int, vector<int>, greater<int> >
	priority_queue <ll, vector <ll> , greater <ll>> q;
	vector <ll> d(n+10, 1e18);
	
	
	d[a[1]]=0;
	q.push(a[1]);
	while (!q.empty()){
		ll x=q.top();
		q.pop();
		for (auto l:g[x]){
			if (d[l.ff] > d[x]+l.ss){
				d[l.ff]=d[x]+l.ss;
				q.push(l.ff);
			}
		}
	}
	ll ans=d[a[2]];
	if (ans == 1e18) ans=-1;
	cout << ans;
	return ;
}
int main()
{
	ios;
	int t=1;
//	cin >> t;
	while (t--){
	     solve();
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 70740 KB Output is correct
2 Correct 36 ms 70752 KB Output is correct
3 Correct 35 ms 70780 KB Output is correct
4 Correct 35 ms 70732 KB Output is correct
5 Correct 34 ms 70736 KB Output is correct
6 Correct 34 ms 70740 KB Output is correct
7 Correct 34 ms 70684 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 70744 KB Output is correct
2 Correct 35 ms 70764 KB Output is correct
3 Correct 34 ms 70740 KB Output is correct
4 Correct 35 ms 70732 KB Output is correct
5 Correct 34 ms 70732 KB Output is correct
6 Correct 35 ms 70760 KB Output is correct
7 Correct 40 ms 70640 KB Output is correct
8 Correct 34 ms 70760 KB Output is correct
9 Correct 35 ms 70772 KB Output is correct
10 Correct 37 ms 70816 KB Output is correct
11 Correct 35 ms 71048 KB Output is correct
12 Correct 36 ms 70740 KB Output is correct
13 Correct 36 ms 70992 KB Output is correct
14 Correct 36 ms 70896 KB Output is correct
15 Correct 36 ms 71000 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 70732 KB Output is correct
2 Correct 36 ms 70672 KB Output is correct
3 Correct 35 ms 70696 KB Output is correct
4 Correct 35 ms 70676 KB Output is correct
5 Correct 35 ms 70664 KB Output is correct
6 Correct 35 ms 70712 KB Output is correct
7 Correct 36 ms 70756 KB Output is correct
8 Correct 36 ms 70688 KB Output is correct
9 Correct 34 ms 70740 KB Output is correct
10 Correct 36 ms 70704 KB Output is correct
11 Correct 36 ms 71040 KB Output is correct
12 Correct 35 ms 70764 KB Output is correct
13 Correct 36 ms 70984 KB Output is correct
14 Correct 36 ms 70996 KB Output is correct
15 Correct 36 ms 70972 KB Output is correct
16 Correct 36 ms 70828 KB Output is correct
17 Correct 41 ms 71340 KB Output is correct
18 Correct 36 ms 70988 KB Output is correct
19 Correct 35 ms 70932 KB Output is correct
20 Correct 112 ms 135064 KB Output is correct
21 Correct 36 ms 70868 KB Output is correct
22 Correct 34 ms 70892 KB Output is correct
23 Correct 36 ms 70980 KB Output is correct
24 Correct 37 ms 71112 KB Output is correct
25 Correct 37 ms 71080 KB Output is correct
26 Correct 37 ms 71104 KB Output is correct
27 Correct 35 ms 70908 KB Output is correct
28 Correct 36 ms 71244 KB Output is correct
29 Correct 37 ms 72140 KB Output is correct
30 Correct 37 ms 71296 KB Output is correct
31 Correct 37 ms 71612 KB Output is correct
32 Correct 36 ms 71316 KB Output is correct
33 Correct 39 ms 73292 KB Output is correct
34 Correct 40 ms 73268 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 70760 KB Output is correct
2 Correct 36 ms 70684 KB Output is correct
3 Correct 36 ms 70716 KB Output is correct
4 Correct 35 ms 70732 KB Output is correct
5 Correct 34 ms 70720 KB Output is correct
6 Correct 34 ms 70708 KB Output is correct
7 Correct 36 ms 70712 KB Output is correct
8 Correct 36 ms 70700 KB Output is correct
9 Correct 34 ms 70740 KB Output is correct
10 Correct 35 ms 70740 KB Output is correct
11 Correct 36 ms 70944 KB Output is correct
12 Correct 36 ms 70800 KB Output is correct
13 Correct 36 ms 70960 KB Output is correct
14 Correct 36 ms 70960 KB Output is correct
15 Correct 36 ms 70972 KB Output is correct
16 Correct 35 ms 70832 KB Output is correct
17 Correct 38 ms 71256 KB Output is correct
18 Correct 36 ms 70856 KB Output is correct
19 Correct 36 ms 70924 KB Output is correct
20 Correct 113 ms 135028 KB Output is correct
21 Correct 36 ms 70856 KB Output is correct
22 Correct 36 ms 70924 KB Output is correct
23 Correct 36 ms 70976 KB Output is correct
24 Correct 38 ms 71184 KB Output is correct
25 Correct 36 ms 71016 KB Output is correct
26 Correct 35 ms 70996 KB Output is correct
27 Correct 34 ms 70924 KB Output is correct
28 Correct 35 ms 71252 KB Output is correct
29 Correct 37 ms 72104 KB Output is correct
30 Correct 38 ms 71300 KB Output is correct
31 Correct 37 ms 71608 KB Output is correct
32 Correct 36 ms 71368 KB Output is correct
33 Correct 40 ms 73260 KB Output is correct
34 Correct 41 ms 73232 KB Output is correct
35 Correct 51 ms 75052 KB Output is correct
36 Correct 40 ms 71384 KB Output is correct
37 Correct 54 ms 78076 KB Output is correct
38 Correct 60 ms 77388 KB Output is correct
39 Correct 58 ms 77772 KB Output is correct
40 Correct 56 ms 77360 KB Output is correct
41 Correct 55 ms 77100 KB Output is correct
42 Correct 41 ms 71252 KB Output is correct
43 Correct 40 ms 71084 KB Output is correct
44 Correct 116 ms 135272 KB Output is correct
45 Correct 58 ms 80536 KB Output is correct
46 Correct 60 ms 80604 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 70760 KB Output is correct
2 Correct 36 ms 70724 KB Output is correct
3 Correct 35 ms 70652 KB Output is correct
4 Correct 34 ms 70736 KB Output is correct
5 Correct 36 ms 70672 KB Output is correct
6 Correct 36 ms 70700 KB Output is correct
7 Correct 37 ms 70760 KB Output is correct
8 Correct 35 ms 70776 KB Output is correct
9 Correct 36 ms 70684 KB Output is correct
10 Correct 35 ms 70760 KB Output is correct
11 Correct 37 ms 70996 KB Output is correct
12 Correct 38 ms 70672 KB Output is correct
13 Correct 38 ms 70940 KB Output is correct
14 Correct 37 ms 70996 KB Output is correct
15 Correct 35 ms 70964 KB Output is correct
16 Correct 36 ms 70800 KB Output is correct
17 Correct 38 ms 71340 KB Output is correct
18 Correct 35 ms 70996 KB Output is correct
19 Correct 39 ms 70912 KB Output is correct
20 Correct 108 ms 135064 KB Output is correct
21 Correct 36 ms 70860 KB Output is correct
22 Correct 38 ms 70824 KB Output is correct
23 Correct 36 ms 70908 KB Output is correct
24 Correct 36 ms 71140 KB Output is correct
25 Correct 37 ms 71064 KB Output is correct
26 Correct 36 ms 71084 KB Output is correct
27 Correct 35 ms 70940 KB Output is correct
28 Correct 37 ms 71340 KB Output is correct
29 Correct 38 ms 72160 KB Output is correct
30 Correct 36 ms 71268 KB Output is correct
31 Correct 37 ms 71592 KB Output is correct
32 Correct 36 ms 71284 KB Output is correct
33 Correct 41 ms 73272 KB Output is correct
34 Correct 41 ms 73316 KB Output is correct
35 Correct 48 ms 75092 KB Output is correct
36 Correct 37 ms 71372 KB Output is correct
37 Correct 59 ms 78072 KB Output is correct
38 Correct 59 ms 77236 KB Output is correct
39 Correct 62 ms 77696 KB Output is correct
40 Correct 60 ms 77388 KB Output is correct
41 Correct 54 ms 77128 KB Output is correct
42 Correct 39 ms 71244 KB Output is correct
43 Correct 39 ms 71128 KB Output is correct
44 Correct 116 ms 135276 KB Output is correct
45 Correct 60 ms 80556 KB Output is correct
46 Correct 59 ms 80512 KB Output is correct
47 Correct 126 ms 94744 KB Output is correct
48 Correct 47 ms 76584 KB Output is correct
49 Correct 47 ms 74732 KB Output is correct
50 Correct 45 ms 74480 KB Output is correct
51 Correct 143 ms 81972 KB Output is correct
52 Execution timed out 1096 ms 113576 KB Time limit exceeded
53 Halted 0 ms 0 KB -