oj.uz

Submission #470668

# Submission time Handle Problem Language Result Execution time Memory
470668 2021-09-04T19:13:38 Z robell Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 354 ms 180992 KB 
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
#define pb push_back
#define eb emplace_back
#define countbits __builtin_popcount
#define beg0 __builtin_clz
#define terminal0 __builtin_ctz
#define mod 1e9+7
void setIO(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}
void setIO(string f){
	freopen((f+".in").c_str(),"r",stdin);
	freopen((f+".out").c_str(),"w",stdout);
	setIO();
}
int jmp[2020][2020];
int b[2020];
int p[2020];
int N, M;
vector<pair<int,int>> adj[2020][2020];
int main(){
	setIO();
	cin >> N >> M;
	for (int i=0;i<M;i++){
		cin >> b[i] >> p[i];
		for (int j=b[i]-p[i];j>=0;j-=p[i]){
			adj[j+p[i]][p[i]].pb({j,p[i]});
			adj[j+p[i]][p[i]].pb({j,2010});
		}
		for (int j=b[i]+p[i];j<N;j+=p[i]){
			adj[j-p[i]][p[i]].pb({j,p[i]});
			adj[j-p[i]][p[i]].pb({j,2010});
		}
		adj[b[i]][2010].pb({b[i],p[i]});
		adj[b[i]][p[i]].pb({b[i],2010});
	}
	memset(jmp,-1,sizeof(jmp));
	jmp[b[0]][2010]=0;
	jmp[b[0]][p[0]]=0;
	deque<pair<int,int>> q;
	q.push_back({b[0],p[0]});
	q.push_back({b[0],2010});
	while (!q.empty()){
		pair<int,int> n = q.front();
		q.pop_front();
		int c = 1;
		if (n.second==2010){
			c=0;
		}
		for (pair<int,int> s:adj[n.first][n.second]){
			if ((jmp[s.first][s.second]==-1)||(jmp[s.first][s.second]>jmp[s.first][s.second]+c)){
				jmp[s.first][s.second]=c+jmp[n.first][n.second];
				if (c==0){
					q.push_front({s.first,s.second});
				}else{
					q.push_back({s.first,s.second});
				}
			}
		}
	}
	cout << jmp[b[1]][p[1]] << "\n";
}

Compilation message

skyscraper.cpp: In function 'void setIO(std::string)':
skyscraper.cpp:19:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  freopen((f+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:20:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  freopen((f+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 112068 KB Output is correct
2 Correct 58 ms 111988 KB Output is correct
3 Correct 59 ms 111992 KB Output is correct
4 Correct 61 ms 112028 KB Output is correct
5 Correct 57 ms 112072 KB Output is correct
6 Correct 59 ms 112032 KB Output is correct
7 Correct 59 ms 112068 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 111976 KB Output is correct
2 Correct 58 ms 112024 KB Output is correct
3 Correct 60 ms 112020 KB Output is correct
4 Correct 58 ms 112016 KB Output is correct
5 Correct 59 ms 112000 KB Output is correct
6 Correct 63 ms 112072 KB Output is correct
7 Correct 58 ms 112084 KB Output is correct
8 Correct 57 ms 112072 KB Output is correct
9 Correct 60 ms 112092 KB Output is correct
10 Correct 63 ms 112168 KB Output is correct
11 Correct 61 ms 112288 KB Output is correct
12 Correct 65 ms 115460 KB Output is correct
13 Correct 66 ms 115544 KB Output is correct
14 Correct 58 ms 112324 KB Output is correct
15 Correct 59 ms 112284 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 112036 KB Output is correct
2 Correct 64 ms 111972 KB Output is correct
3 Correct 58 ms 112068 KB Output is correct
4 Correct 58 ms 111988 KB Output is correct
5 Correct 58 ms 112024 KB Output is correct
6 Correct 58 ms 112036 KB Output is correct
7 Correct 58 ms 112068 KB Output is correct
8 Correct 57 ms 111992 KB Output is correct
9 Correct 62 ms 112108 KB Output is correct
10 Correct 62 ms 112088 KB Output is correct
11 Correct 60 ms 112328 KB Output is correct
12 Correct 75 ms 115552 KB Output is correct
13 Correct 72 ms 115580 KB Output is correct
14 Correct 60 ms 112300 KB Output is correct
15 Correct 61 ms 112396 KB Output is correct
16 Correct 59 ms 112236 KB Output is correct
17 Correct 64 ms 112700 KB Output is correct
18 Correct 60 ms 112284 KB Output is correct
19 Correct 60 ms 112256 KB Output is correct
20 Correct 317 ms 180992 KB Output is correct
21 Correct 61 ms 112196 KB Output is correct
22 Correct 59 ms 112228 KB Output is correct
23 Correct 61 ms 112240 KB Output is correct
24 Correct 64 ms 112452 KB Output is correct
25 Correct 62 ms 112368 KB Output is correct
26 Correct 305 ms 176872 KB Output is correct
27 Correct 289 ms 175220 KB Output is correct
28 Correct 67 ms 112776 KB Output is correct
29 Correct 86 ms 114016 KB Output is correct
30 Correct 65 ms 112672 KB Output is correct
31 Correct 68 ms 113172 KB Output is correct
32 Correct 66 ms 112776 KB Output is correct
33 Correct 94 ms 115844 KB Output is correct
34 Correct 93 ms 115868 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 112036 KB Output is correct
2 Correct 60 ms 112000 KB Output is correct
3 Correct 59 ms 112100 KB Output is correct
4 Correct 66 ms 112088 KB Output is correct
5 Correct 59 ms 112064 KB Output is correct
6 Correct 59 ms 111984 KB Output is correct
7 Correct 62 ms 112060 KB Output is correct
8 Correct 63 ms 112000 KB Output is correct
9 Correct 59 ms 112068 KB Output is correct
10 Correct 61 ms 112076 KB Output is correct
11 Correct 59 ms 112280 KB Output is correct
12 Correct 75 ms 115508 KB Output is correct
13 Correct 68 ms 115528 KB Output is correct
14 Correct 60 ms 112224 KB Output is correct
15 Correct 60 ms 112232 KB Output is correct
16 Correct 60 ms 112284 KB Output is correct
17 Correct 65 ms 112664 KB Output is correct
18 Correct 64 ms 112328 KB Output is correct
19 Correct 60 ms 112192 KB Output is correct
20 Correct 325 ms 180896 KB Output is correct
21 Correct 59 ms 112128 KB Output is correct
22 Correct 59 ms 112284 KB Output is correct
23 Correct 62 ms 112260 KB Output is correct
24 Correct 64 ms 112548 KB Output is correct
25 Correct 62 ms 112376 KB Output is correct
26 Correct 298 ms 176804 KB Output is correct
27 Correct 284 ms 175304 KB Output is correct
28 Correct 68 ms 112788 KB Output is correct
29 Correct 89 ms 113988 KB Output is correct
30 Correct 63 ms 112564 KB Output is correct
31 Correct 71 ms 113220 KB Output is correct
32 Correct 66 ms 112780 KB Output is correct
33 Correct 95 ms 115880 KB Output is correct
34 Correct 102 ms 115816 KB Output is correct
35 Incorrect 110 ms 116804 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 112180 KB Output is correct
2 Correct 66 ms 112056 KB Output is correct
3 Correct 59 ms 112068 KB Output is correct
4 Correct 62 ms 112076 KB Output is correct
5 Correct 58 ms 112092 KB Output is correct
6 Correct 59 ms 112076 KB Output is correct
7 Correct 57 ms 112068 KB Output is correct
8 Correct 64 ms 111980 KB Output is correct
9 Correct 65 ms 112084 KB Output is correct
10 Correct 60 ms 112172 KB Output is correct
11 Correct 60 ms 112324 KB Output is correct
12 Correct 64 ms 115424 KB Output is correct
13 Correct 67 ms 115596 KB Output is correct
14 Correct 65 ms 112280 KB Output is correct
15 Correct 59 ms 112280 KB Output is correct
16 Correct 58 ms 112180 KB Output is correct
17 Correct 65 ms 112708 KB Output is correct
18 Correct 61 ms 112344 KB Output is correct
19 Correct 63 ms 112252 KB Output is correct
20 Correct 354 ms 180972 KB Output is correct
21 Correct 59 ms 112172 KB Output is correct
22 Correct 60 ms 112228 KB Output is correct
23 Correct 61 ms 112220 KB Output is correct
24 Correct 65 ms 112516 KB Output is correct
25 Correct 63 ms 112652 KB Output is correct
26 Correct 297 ms 176768 KB Output is correct
27 Correct 284 ms 175244 KB Output is correct
28 Correct 70 ms 112888 KB Output is correct
29 Correct 81 ms 114064 KB Output is correct
30 Correct 64 ms 112656 KB Output is correct
31 Correct 73 ms 113084 KB Output is correct
32 Correct 67 ms 112836 KB Output is correct
33 Correct 93 ms 115920 KB Output is correct
34 Correct 96 ms 115844 KB Output is correct
35 Incorrect 113 ms 116804 KB Output isn't correct
36 Halted 0 ms 0 KB -