oj.uz

Submission #49174

# Submission time Handle Problem Language Result Execution time Memory
49174 2018-05-23T05:10:04 Z Namnamseo Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n, m;
vector<int> b[30010];

const int Lim = 120;
const int V = 30000*(Lim + 1);

int dist[V];
vector<pp> edge[V];

vector<int> usable[30010];

int main()
{
	read(n, m);
	int tg = 0, sp = 0;
	for(int i=0; i<m; ++i){
		int b, p;
		read(b, p);
		if(i == 0) sp = b;
		if(i == 1) tg = b;
		
		if(p <= Lim) ::b[p].pb(b);
		else usable[b].pb(p);
	}
	
	for(int p=1; p<=Lim; ++p) if(b[p].size()){
		for(int a:b[p]) edge[a].eb(p*n+a, 0);
		for(int i=0; i<n; ++i){
			if(i+p < n) edge[p*n+i].eb(p*n+(i+p), 1);
			if(i-p >=0) edge[p*n+i].eb(p*n+(i-p), 1);
			edge[p*n+i].eb(i, 0);
		}
	}
	
	fill(dist, dist+V, 1e9);
	priority_queue<pp> pq;
	dist[sp] = 0;
	pq.emplace(0, sp);
	
	while(pq.size()){
		int md, x; tie(md, x) = pq.top(); pq.pop();
		md = -md;
		if(md != dist[x]) continue;
		
		auto relax = [&](int y, int d){
			if(dist[y] > d){
				dist[y] = d;
				pq.emplace(-d, y);
			}
		};
		for(auto et:edge[x]) relax(et.x, md+et.y);
		
		if(x < n){
			for(int p:usable[x]){
				for(int i=1;;++i) if(x-p*i>=0) relax(x-p*i, md+i); else break;
				for(int i=1;;++i) if(x+p*i<n) relax(x+p*i, md+i); else break;
			}
		}
	}
	
	int ans = dist[tg];
	if(ans == 1e9) ans = -1;
	printf("%d\n", ans);
	return 0;
}

Compilation message

skyscraper.cpp: In function 'void read(int&)':
skyscraper.cpp:6:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~
skyscraper.cpp: In function 'void read(ll&)':
skyscraper.cpp:7:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                   ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 101240 KB Output is correct
2 Correct 84 ms 101340 KB Output is correct
3 Correct 102 ms 101340 KB Output is correct
4 Correct 87 ms 101344 KB Output is correct
5 Correct 103 ms 101344 KB Output is correct
6 Correct 103 ms 101396 KB Output is correct
7 Correct 87 ms 101396 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 101448 KB Output is correct
2 Correct 92 ms 101448 KB Output is correct
3 Correct 93 ms 101460 KB Output is correct
4 Correct 83 ms 101460 KB Output is correct
5 Correct 95 ms 101516 KB Output is correct
6 Correct 91 ms 101516 KB Output is correct
7 Correct 110 ms 101516 KB Output is correct
8 Correct 91 ms 101516 KB Output is correct
9 Correct 96 ms 101608 KB Output is correct
10 Correct 91 ms 101804 KB Output is correct
11 Correct 92 ms 101868 KB Output is correct
12 Correct 90 ms 101868 KB Output is correct
13 Correct 88 ms 101868 KB Output is correct
14 Correct 104 ms 101868 KB Output is correct
15 Correct 95 ms 101868 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 101868 KB Output is correct
2 Correct 90 ms 101868 KB Output is correct
3 Correct 86 ms 101868 KB Output is correct
4 Correct 99 ms 101868 KB Output is correct
5 Correct 86 ms 101868 KB Output is correct
6 Correct 93 ms 101868 KB Output is correct
7 Correct 88 ms 101868 KB Output is correct
8 Correct 85 ms 101868 KB Output is correct
9 Correct 84 ms 101868 KB Output is correct
10 Correct 87 ms 101868 KB Output is correct
11 Correct 91 ms 101884 KB Output is correct
12 Correct 98 ms 101884 KB Output is correct
13 Correct 94 ms 101884 KB Output is correct
14 Correct 98 ms 101884 KB Output is correct
15 Correct 94 ms 101928 KB Output is correct
16 Correct 103 ms 102396 KB Output is correct
17 Correct 136 ms 105336 KB Output is correct
18 Correct 109 ms 106364 KB Output is correct
19 Correct 93 ms 106364 KB Output is correct
20 Correct 88 ms 106364 KB Output is correct
21 Correct 89 ms 106364 KB Output is correct
22 Correct 113 ms 106364 KB Output is correct
23 Correct 115 ms 106364 KB Output is correct
24 Correct 116 ms 108540 KB Output is correct
25 Correct 88 ms 108540 KB Output is correct
26 Correct 117 ms 108540 KB Output is correct
27 Correct 142 ms 108540 KB Output is correct
28 Correct 159 ms 108540 KB Output is correct
29 Correct 118 ms 108540 KB Output is correct
30 Correct 104 ms 108540 KB Output is correct
31 Correct 106 ms 108540 KB Output is correct
32 Correct 96 ms 108540 KB Output is correct
33 Correct 119 ms 108540 KB Output is correct
34 Correct 126 ms 108540 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 108540 KB Output is correct
2 Correct 84 ms 108540 KB Output is correct
3 Correct 83 ms 108540 KB Output is correct
4 Correct 92 ms 108540 KB Output is correct
5 Correct 100 ms 108540 KB Output is correct
6 Correct 87 ms 108540 KB Output is correct
7 Correct 93 ms 108540 KB Output is correct
8 Correct 93 ms 108540 KB Output is correct
9 Correct 92 ms 108540 KB Output is correct
10 Correct 93 ms 108540 KB Output is correct
11 Correct 92 ms 108540 KB Output is correct
12 Correct 89 ms 108540 KB Output is correct
13 Correct 88 ms 108540 KB Output is correct
14 Correct 91 ms 108540 KB Output is correct
15 Correct 94 ms 108540 KB Output is correct
16 Correct 90 ms 108540 KB Output is correct
17 Correct 111 ms 108540 KB Output is correct
18 Correct 114 ms 108540 KB Output is correct
19 Correct 101 ms 108540 KB Output is correct
20 Correct 90 ms 108540 KB Output is correct
21 Correct 101 ms 108540 KB Output is correct
22 Correct 158 ms 108540 KB Output is correct
23 Correct 106 ms 108540 KB Output is correct
24 Correct 122 ms 108540 KB Output is correct
25 Correct 91 ms 108540 KB Output is correct
26 Correct 119 ms 108540 KB Output is correct
27 Correct 93 ms 108540 KB Output is correct
28 Correct 112 ms 108540 KB Output is correct
29 Correct 105 ms 108540 KB Output is correct
30 Correct 89 ms 108540 KB Output is correct
31 Correct 96 ms 108540 KB Output is correct
32 Correct 92 ms 108540 KB Output is correct
33 Correct 137 ms 108540 KB Output is correct
34 Correct 138 ms 108540 KB Output is correct
35 Correct 150 ms 109564 KB Output is correct
36 Correct 156 ms 109564 KB Output is correct
37 Correct 158 ms 112436 KB Output is correct
38 Correct 162 ms 112852 KB Output is correct
39 Correct 189 ms 112852 KB Output is correct
40 Correct 161 ms 112852 KB Output is correct
41 Correct 178 ms 112852 KB Output is correct
42 Correct 126 ms 112852 KB Output is correct
43 Correct 111 ms 112852 KB Output is correct
44 Correct 105 ms 112852 KB Output is correct
45 Correct 188 ms 112892 KB Output is correct
46 Correct 190 ms 112892 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 112892 KB Output is correct
2 Correct 110 ms 112892 KB Output is correct
3 Correct 84 ms 112892 KB Output is correct
4 Correct 82 ms 112892 KB Output is correct
5 Correct 82 ms 112892 KB Output is correct
6 Correct 94 ms 112892 KB Output is correct
7 Correct 81 ms 112892 KB Output is correct
8 Correct 85 ms 112892 KB Output is correct
9 Correct 84 ms 112892 KB Output is correct
10 Correct 94 ms 112892 KB Output is correct
11 Correct 84 ms 112892 KB Output is correct
12 Correct 94 ms 112892 KB Output is correct
13 Correct 90 ms 112892 KB Output is correct
14 Correct 90 ms 112892 KB Output is correct
15 Correct 93 ms 112892 KB Output is correct
16 Correct 90 ms 112892 KB Output is correct
17 Correct 109 ms 112892 KB Output is correct
18 Correct 107 ms 112892 KB Output is correct
19 Correct 99 ms 112892 KB Output is correct
20 Correct 89 ms 112892 KB Output is correct
21 Correct 96 ms 112892 KB Output is correct
22 Correct 115 ms 112892 KB Output is correct
23 Correct 98 ms 112892 KB Output is correct
24 Correct 163 ms 112892 KB Output is correct
25 Correct 85 ms 112892 KB Output is correct
26 Correct 103 ms 112892 KB Output is correct
27 Correct 101 ms 112892 KB Output is correct
28 Correct 111 ms 112892 KB Output is correct
29 Correct 105 ms 112892 KB Output is correct
30 Correct 87 ms 112892 KB Output is correct
31 Correct 98 ms 112892 KB Output is correct
32 Correct 93 ms 112892 KB Output is correct
33 Correct 119 ms 112892 KB Output is correct
34 Correct 120 ms 112892 KB Output is correct
35 Correct 135 ms 112892 KB Output is correct
36 Correct 115 ms 112892 KB Output is correct
37 Correct 166 ms 112892 KB Output is correct
38 Correct 184 ms 112932 KB Output is correct
39 Correct 164 ms 112932 KB Output is correct
40 Correct 166 ms 112932 KB Output is correct
41 Correct 182 ms 113004 KB Output is correct
42 Correct 123 ms 113004 KB Output is correct
43 Correct 105 ms 113004 KB Output is correct
44 Correct 91 ms 113004 KB Output is correct
45 Correct 166 ms 113004 KB Output is correct
46 Correct 180 ms 113012 KB Output is correct
47 Correct 546 ms 171640 KB Output is correct
48 Correct 427 ms 183676 KB Output is correct
49 Correct 333 ms 183676 KB Output is correct
50 Correct 339 ms 183676 KB Output is correct
51 Correct 598 ms 203888 KB Output is correct
52 Correct 618 ms 224892 KB Output is correct
53 Correct 118 ms 224892 KB Output is correct
54 Correct 89 ms 224892 KB Output is correct
55 Correct 108 ms 224892 KB Output is correct
56 Correct 109 ms 224892 KB Output is correct
57 Correct 346 ms 224892 KB Output is correct
58 Correct 170 ms 224892 KB Output is correct
59 Correct 279 ms 224892 KB Output is correct
60 Correct 418 ms 224892 KB Output is correct
61 Correct 263 ms 224892 KB Output is correct
62 Correct 487 ms 224892 KB Output is correct
63 Correct 118 ms 224892 KB Output is correct
64 Correct 112 ms 224892 KB Output is correct
65 Correct 344 ms 224892 KB Output is correct
66 Execution timed out 1105 ms 262144 KB Time limit exceeded
67 Halted 0 ms 0 KB -