oj.uz

Submission #552630

# Submission time Handle Problem Language Result Execution time Memory
552630 2022-04-23T12:52:09 Z QwertyPi Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 2 ms 1708 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
int dp[30001];
vector<int> G[30001];
int A[30001][2];
int l[30001], r[30001];

vector<pii> H[30001];
int main(){
	int n, k;
	cin >> n >> k;
	set<pii> M;
	for(int i = 0; i < k; i++){
		cin >> A[i][0] >> A[i][1];
		if(i >= 2 && M.count({A[i][0], A[i][1]})){
			continue;
		}
		M.insert({A[i][0], A[i][1]});
		G[A[i][0]].push_back(i);
		H[A[i][1]].push_back({A[i][0], i});
	}
	for(int i = 1; i <= 30000; i++){
		sort(H[i].begin(), H[i].end(), [&i](pii aa, pii bb){
			int a = aa.fi, b = bb.fi;
			return a % i < b % i || a % i == b % i && a < b; 
		});
		if(H[i].size() == 0) continue;
		l[H[i].front().se] = H[i].front().fi % i;
		for(int j = 0; j + 1 < H[i].size(); j++){
			if(H[i][j].fi % i == H[i][j + 1].fi % i){
				r[H[i][j].se] = H[i][j + 1].fi;
				l[H[i][j + 1].se] = H[i][j].fi;
			}
		}
		r[H[i].back().se] = n - 1;
	}
//	for(int i = 0; i < k; i++){
//		cout << l[i] << ' ' << r[i] << endl;
//	}
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
	q.push({0, A[0][0], 1 << 30});
	fill(dp, dp + n, 1 << 30);
	while(q.size()){
		tuple<int, int, int> qe = q.top(); q.pop();
		int w = get<0>(qe), v = get<1>(qe), ban = get<2>(qe);
		if(dp[v] != (1 << 30)) continue;
		dp[v] = w;
		for(auto i : G[v]){
			for(int j = l[i]; j <= r[i]; j += A[i][1]){
				int d = abs(v - j) / A[i][1];
				if(dp[j] > w + d) q.push({w + d, j, i});
			}
		}
	}
	cout << (dp[A[1][0]] == (1 << 30) ? -1 : dp[A[1][0]]) << endl;
}

Compilation message

skyscraper.cpp: In lambda function:
skyscraper.cpp:28:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   28 |    return a % i < b % i || a % i == b % i && a < b;
      |                            ~~~~~~~~~~~~~~~^~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int j = 0; j + 1 < H[i].size(); j++){
      |                  ~~~~~~^~~~~~~~~~~~~
skyscraper.cpp:48:39: warning: unused variable 'ban' [-Wunused-variable]
   48 |   int w = get<0>(qe), v = get<1>(qe), ban = get<2>(qe);
      |                                       ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 2 ms 1652 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Incorrect 2 ms 1708 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 2 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Incorrect 1 ms 1620 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Incorrect 1 ms 1620 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Incorrect 1 ms 1620 KB Output isn't correct
10 Halted 0 ms 0 KB -