oj.uz

답안 #1028630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1028630 2024-07-20T06:30:04 Z vjudge1 Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 6 ms 1304 KB 
#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();
      //  cerr << f << ' ' << s << ' ' << dist[f][s] << endl;
      if(cnt[f] <= 1000) {
	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_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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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

# 결과 실행 시간 메모리 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 Correct 2 ms 604 KB Output is correct
11 Incorrect 6 ms 1116 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 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 Correct 2 ms 604 KB Output is correct
11 Incorrect 5 ms 1292 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 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 344 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 Correct 2 ms 604 KB Output is correct
11 Incorrect 5 ms 1296 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 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 344 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 Correct 2 ms 620 KB Output is correct
11 Incorrect 6 ms 1304 KB Output isn't correct
12 Halted 0 ms 0 KB -