Submission #555976

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
555976	2022-05-02T05:28:58 Z	MurotY	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1000 ms	135276 KB

skyscraper

// 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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-

Submission #555976

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 21.0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
14.0 / 14.0

Subtask #4
21.0 / 21.0

Subtask #5
0 / 43.0