oj.uz

Submission #470129

# Submission time Handle Problem Language Result Execution time Memory
470129 2021-09-03T05:02:38 Z robell Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 1000 ms 38660 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
int 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 N, M;
vector<vector<int>> l;
vector<pair<int,int>> m;
vector<set<int>> pos;
int main(){
	setIO();
	cin >> N >> M;
	for (int i=0;i<N;i++) l.pb(vector<int>());
	for (int i=0;i<M;i++){
		int pos; cin >> pos;
		int moves; cin >> moves;
		m.pb({pos,moves});
	}
	int dp[M][N];
	for (int i=0;i<M;i++){
		for (int j=0;j<N;j++){
			dp[i][j]=1e9;
		}
	}
	queue<pair<pair<int,int>,pair<int,int>>> q;
	q.push({{m[0].first,m[0].second},{0,0}});
	while (!q.empty()){
		int pos=q.front().first.first;
		int jmp = q.front().first.second;
		int dist = q.front().second.first;
		int ind = q.front().second.second;
		q.pop();
		if (dp[ind][pos]<dist) continue;
		dp[ind][pos]=dist;
		if (pos+jmp<N){
			if (dp[ind][pos+jmp]>dist+1) q.push({{pos+jmp,jmp},{dist+1,ind}});
		}
		if (pos-jmp>=0){
			if (dp[ind][pos-jmp]>dist+1) q.push({{pos-jmp,jmp},{dist+1,ind}});
		}
		for (int i=0;i<M;i++){
			if (i==ind) continue;
			if (m[i].first==pos){
				if (dp[i][pos]>dist){
					q.push({{pos,m[i].second},{dist,i}});
				}
			}
		}
	}
	int totmin = 1e9;
	for (int i=0;i<N;i++){
		totmin=min(totmin,dp[1][i]);
	}
	cout << (totmin==1e9?-1:totmin) << "\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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 1 ms 312 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 11 ms 460 KB Output is correct
11 Correct 738 ms 2024 KB Output is correct
12 Execution timed out 1091 ms 38432 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 10 ms 460 KB Output is correct
11 Correct 742 ms 2012 KB Output is correct
12 Execution timed out 1085 ms 38596 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 316 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 10 ms 516 KB Output is correct
11 Correct 734 ms 2196 KB Output is correct
12 Execution timed out 1095 ms 38660 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 10 ms 460 KB Output is correct
11 Correct 744 ms 2004 KB Output is correct
12 Execution timed out 1097 ms 38524 KB Time limit exceeded
13 Halted 0 ms 0 KB -