oj.uz

Submission #786104

# Submission time Handle Problem Language Result Execution time Memory
786104 2023-07-18T03:31:19 Z makanhulia Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1 ms 980 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl "\n"
#define pii pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define pque priority_queue
#define pqueg priority_queue<ll,vector<ll>,greater<ll>>
#define que queue<ll>
#define FOR(m,i,n) for(int i=(m); i<=(n); i++)
#define FORM(m,i,n) for(int i=(m); i>=(n); i--)
ll n,m;
pii a[30300];
vector<pii> adj[30300];
priority_queue<pii,vector<pii>,greater<pii>> pq;
ll dist[30030];
bool vis[30030];
int main() {
//  ios_base::sync_with_stdio(0);
//  cin.tie(0);
  cin >> n >> m;
  FOR(1,i,m) {
    cin >> a[i].fi >> a[i].se;
  }
  sort(a+1,a+m+1);
  FOR(1,i,m) {
    FOR(1,j,m) {
      if(a[i].fi == a[j].fi) continue;
      if(abs(a[i].fi - a[j].fi) % a[i].se == 0) {
        adj[a[i].fi].pb({a[j].fi,abs(a[i].fi - a[j].fi) / a[i].se});
      }
    }
  }
//  FOR(1,i,4) {
//    cout << i << ": ";
//    for(auto i : adj[i]) {
//      cout << i.fi << " " << i.se << endl;
//    }
//    cout << endl;
//  }
  pq.push({0,0});
  FOR(1,i,n) {
    dist[i] = 1e9;
  }
  while(!pq.empty()) {
    pii x = pq.top();
    pq.pop();
    for(auto i : adj[x.se]) {
//      if(!vis[i.fi]) {
//        vis[i.fi] = true;
        if(dist[i.fi] > dist[x.se] + i.se) {
          dist[i.fi] = dist[x.se] + i.se;
          pq.push({dist[i.fi],i.fi});
        }
//      }
    }
  }
  if(dist[1] == 1e9) {
    cout << -1 << endl;
  }
  else {
    cout << dist[1] << endl;
  }
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 43.0

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