oj.uz

Submission #373803

# Submission time Handle Problem Language Result Execution time Memory
373803 2021-03-05T19:30:02 Z victoriad Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 1 ms 492 KB 
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
using namespace std;

int d(int x,int y,vector<vector<pair<int,int> > >&s){
  int N=s.size();
  vector<int>dis(N,1e9);
  dis[x]=0;
  priority_queue<pair<int,int> >pq;
  pq.push(make_pair(0,x));
  while(!pq.empty()){
    int nodo=pq.top().second;
    int d=-pq.top().first;
    pq.pop();
    if(d>dis[nodo])
      continue;
    dis[nodo]=d;
    for(pair<int,int>v:s[nodo]){
      int vec=v.first;
      int dv=v.second;
      if(dis[vec]>dis[nodo]+dv){
        dis[vec]=dis[nodo]+dv;
        pq.push(make_pair(-dis[vec],vec));
      }
    }

  }
  if(dis[y]==1e9){
    return -1;
  }
  else{
    return dis[y];
  }
}

int main(){
   ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N,M,B,P;
  cin>>N>>M;
  vector<vector<pair<int,int> > >s(N);
  vector<int>b(M);
  for(int i=0;i<M;i++){
  cin>>B>>P;
  b[i]=B;
  int j=B-P;
  int o=1,u=1;
  while(j>=0){
   s[B].push_back(make_pair(j,o));
    j=j-P;
    o++;
  }
  j=B+P;
   while(j<=N){
    s[B].push_back(make_pair(j,u));
    j=j+P;
    u++;
  }
  }
  int x=b[0];
  int y=b[1];
  cout<<d(x,y,s);
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Runtime error 1 ms 492 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Runtime error 1 ms 492 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Runtime error 1 ms 492 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Runtime error 1 ms 492 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Runtime error 1 ms 492 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -