Submission #1028648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028648		vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	362 ms	262144 KiB

skyscraper

#include<bits/stdc++.h>

using namespace std;

const int inf = 1e9;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  
  int n, m;
  cin >> n >> m;
  
  int dist[n][m];
  for(int i = 0; i < n; i ++)
    for(int j = 0; j < m ; j++)
      dist[i][j] = inf;

  vector<int> L[n];
  int p[m], b[m];
  for(int i = 0; i < m; i ++)
    {
      cin >> b[i] >> p[i];
      L[b[i]].push_back(i);
    }

  int cnt[n] = {};
  deque<pair<int,int> > Q;
  Q.push_back({b[0], 0});
  dist[b[0]][0] = 0;
  while(Q.size())
    {
      int f = Q.front().first, s = Q.front().second;
      Q.pop_front();
      if(f == b[1])
	{
	  cout << dist[f][s] << endl;
	  exit(0);
	}
      // cerr << f << ' ' << s << ' ' << dist[f][s] << endl;
      // if(cnt[f] <= 2000) {
	for(int res : L[f])
	  if(dist[f][s] < dist[f][res])
	    {
	      dist[f][res] = dist[f][s];
	      Q.push_front({f, res});
	    }
	// cnt[f]++;
      // }
      
      L[f].clear();
      
      if(f + p[s] < n && dist[f][s] + 1 < dist[f + p[s]][s])
	{
	  dist[f + p[s]][s] = dist[f][s] + 1;
	  Q.push_back({f + p[s], s});
	}

      if(f - p[s] >= 0 && dist[f][s] + 1 < dist[f - p[s]][s])
	{
	  dist[f - p[s]][s] = dist[f][s] + 1;
	  Q.push_back({f - p[s], s});
	}
    }

  cout << -1 << endl;
  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:28:7: warning: unused variable 'cnt' [-Wunused-variable]
   28 |   int cnt[n] = {};
      |       ^~~

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