oj.uz

답안 #699920

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699920 2023-02-18T10:43:28 Z Abrar_Al_Samit Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1 ms 1040 KB 
#include<bits/stdc++.h>
using namespace std;

const int nax = 3e4 + 3;
const int INF = 1e9;

int b[nax], p[nax];
vector<int>doges[nax];

map<pair<int,int>,int>dist;

int get(int x, int y) {
  if(dist.count(make_pair(x, y))) return dist[{x, y}];
  return INF;
}
void PlayGround() {
  int n, m;
  cin>>n>>m;

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

  dist[{b[0], 0}] = 0;

  queue<tuple<int,int,int>>q;
  q.push({b[0], 0, 0});

  while(!q.empty()) {
    auto x = q.front();
    q.pop();
    int ss = get<0>(x);
    int j = get<1>(x);
    int d = get<2>(x);

    if(d!=get(ss, j)) continue;

    if(j==0) {
      for(int z : doges[ss]) {
        if(get(ss, z)>d) {
          dist[{ss, z}] = d;
          q.emplace(ss, z, d);
        }
      }
    } else {
      if(ss+j<n) {
        if(get(ss+j, j)>d+1) {
          dist[{ss+j, j}] = d+1;
          q.emplace(ss+j, j, d+1);
        }
        if(get(ss+j, 0)>d+1) {
          dist[{ss+j, 0}] = d+1;
          q.emplace(ss+j, 0, d+1);
        }
      }
      if(ss-j>=0) {
        if(get(ss-j, j)>d+1) {
          dist[{ss-j, j}] = d+1;
          q.emplace(ss-j, j, d+1);
        }
        if(get(ss-j, 0)>d+1) {
          dist[{ss-j, 0}] = d+1;
          q.emplace(ss-j, 0, d+1);
        }
      }
    }

  }

  cout<<get(b[1], 0)<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1032 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Incorrect 1 ms 980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Incorrect 1 ms 980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 1036 KB Output is correct
4 Incorrect 1 ms 980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1040 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Incorrect 1 ms 980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 984 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Incorrect 1 ms 1032 KB Output isn't correct
5 Halted 0 ms 0 KB -