Submission #1121294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121294		mmdrzada	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	834 ms	7584 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;
 
typedef vector<int> vi;
typedef vector<char> vc;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
 
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")

#define sep ' '
#define F first
#define S second
#define fastIO   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define pq priority_queue
 
const int N = 3e4+1;
const int T = 175;
int n, m;
int dis[N];
int b[N], p[N];
vector<int> D[N];
bool X[N][T];
bool vis[N];

// check MAXN
int main() {
  fastIO;
  
  
  cin >> n >> m;
  for(int i = 0 ; i < m ; i ++) {
    cin >> b[i] >> p[i];
    if (p[i] < T) X[b[i]][p[i]] = true;
    D[b[i]].pb(p[i]);
  }
	fill(dis, dis+n, n*n+1);
  dis[b[0]] = 0;
  
  
  for(int asd = 0 ; asd < n ; asd ++) {
  	int p, mn = n*n+1;
  	for(int i = 0 ; i < n ; i ++) {
  		if (!vis[i] && dis[i] < mn) {
  			mn = dis[i];
  			p = i;
  		}
  	}
  	if (p == b[1]) break;
  	vis[p] = true;
  	for (int w : D[p]) {
        int l = 0;
        for (int j = p - w; j >= 0; j -= w) {
            dis[j] = min(dis[j], dis[p] + l + 1);
            l++;
        }
        l = 0;
        for (int j = p + w; j < n; j += w) {
            dis[j] = min(dis[j], dis[p] + l + 1);
            l++;
        }
    }
  }
  cout << (m == 0 || dis[b[1]] == n*n+1 ? -1 : dis[b[1]]) << endl;
  
  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:63:39: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |             dis[j] = min(dis[j], dis[p] + l + 1);
      |                                  ~~~~~^

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43