제출 #1192767

#제출 시각아이디문제언어결과실행 시간메모리
1192767GrayJakarta Skyscrapers (APIO15_skyscraper)C++20
100 / 100
303 ms121812 KiB
#include <algorithm> #include <bits/stdc++.h> #include <cassert> #include <vector> using namespace std; #define ll int #define ull unsigned long long #define ld long double #define ff first #define ss second #define ln "\n" #define mp make_pair #define pb push_back #define INF (ll)1e18 ll MOD = 1e9+7; void solve(){ ll n, m; cin >> n >> m; vector<vector<pair<ll, ll>>> avail(n); vector<pair<ll, ll>> d(m); for (ll i=0; i<m; i++){ ll x, p; cin >> x >> p; d[i] = {x, p}; avail[x].push_back({p, i}); } vector<vector<bool>> vis(n, vector<bool>(n+1)); vector<ll> dist(m, INF); queue<tuple<ll, ll, ll>> que; que.push({0, d[0].ff, 0}); while (!que.empty()){ auto [w, x, i]=que.front(); que.pop(); if (vis[x][d[i].ss]) continue; vis[x][d[i].ss]=1; dist[i]=min(dist[i], w); if (x-d[i].ss>=0 and !vis[x-d[i].ss][d[i].ss]) que.push({w+1, x-d[i].ss, i}); if (x+d[i].ss<n and !vis[x+d[i].ss][d[i].ss]) que.push({w+1, x+d[i].ss, i}); for (auto [p, ind]:avail[x]){ dist[ind]=min(dist[ind], w); if (x-d[ind].ss>=0 and !vis[x-d[ind].ss][d[ind].ss]) que.push({w+1, x-d[ind].ss, ind}); if (x+d[ind].ss<n and !vis[x+d[ind].ss][d[ind].ss]) que.push({w+1, x+d[ind].ss, ind}); } } cout << (dist[1]!=INF?dist[1]:-1) << ln; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL auto start = chrono::high_resolution_clock::now(); #endif ll testc=1; // cin >> testc; for (ll __c=1; __c<=testc; __c++) solve(); #ifdef LOCAL auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start); cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...