oj.uz

Submission #249414

# Submission time Handle Problem Language Result Execution time Memory
249414 2020-07-14T22:32:18 Z Marlov Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 0 ms 384 KB 
/*
Code by @marlov       
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

#define INF 200000000
#define maxV 30005

int N,M;
pair<int,int> doge[maxV];
int dist[maxV];
int visited[maxV];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=0;i<M;i++){
        cin>>doge[i].first>>doge[i].second;
        dist[i]=INF;
    }
    //dijkstra's
    priority_queue< pair<int,int>,vector< pair<int,int> >,greater< pair<int,int> > >pq;
    dist[0]=0;
    pq.push( make_pair(0,0) );
    while(!pq.empty()&&!visited[1]){
        int cn=pq.top().second;
        pq.pop();
        if(visited[cn]==true) continue;
        visited[cn]=true;
        for(int i=0;i<N;i++){
            int dtn=abs(doge[cn].first-doge[i].first);
            if(dtn%doge[cn].second==0){
                if(dist[cn]+(dtn/doge[cn].second)<dist[i]){
                    dist[i]=dist[cn]+(dtn/doge[cn].second);
                    pq.push(make_pair(dist[i],i));
                }
            }
        }

    }
    if(dist[1]==INF){
        cout<<-1<<'\n';
    }else{
        cout<<dist[1]<<'\n';
    }

    return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -