Submission #1028616

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1028616	2024-07-20T06:14:34 Z	vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	1 ms	604 KB

skyscraper

#include<bits/stdc++.h>

using namespace std;

const int inf = 1e9;

int main()
{
  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);
    }


  bool seen[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();
      //  cerr << f << ' ' << s << ' ' << dist[f][s] << endl;
      if(!seen[f])
	{
	  for(int res : L[f])
	    if(dist[f][s] < dist[f][res])
	      {
		dist[f][res] = dist[f][s];
		Q.push_front({f, res});
	      }
	  seen[f] = true;
	}
      
      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_front({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_front({f - p[s], s});
	}
    }

  if(dist[b[1]][1] == inf)
    cout << -1 << endl;
  else
    cout << dist[b[1]][1] << endl;
  return 0;
}

Subtask #1

10.0 / 10.0

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

Subtask #2

0 / 12.0

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

Subtask #3

0 / 14.0

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

Subtask #4

0 / 21.0

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

Subtask #5

0 / 43.0

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