제출 #563105

#제출 시각아이디문제언어결과실행 시간메모리
563105khangalJakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
698 ms41944 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; typedef long long ll; typedef double db; typedef vector<long long> vl; typedef pair<long long, long long > pl; const int N = 1e6 + 1; #define po pop_back #define pb push_back #define mk make_pair #define lw lower_bound #define up upper_bound #define ff first #define ss second #define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0); #define MOD 1000000007 #define MAX 1e18 #define MIN -1e18 #define per(i,a,b) for(ll i=b;i>=a;i--) #define con continue #define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout); #define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628 // typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; // template< typename T> // using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; ll n, m, mid, res,pos, mn, mx, sum, h1, h2, arr[3234567],arr1[1234567],k, i, j, h, a, x, y, z,par[1234567]; bool used[1234567]; ll tp[1234567]; ll dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},c1[123][123]; //ll jump[22][223456]; //ll lvl[1234567]; //ll bit[1234567]; //ll timer; //ll st[1234567],endd[1234567]; //ll dp[5005][5005]; vl dog[1234567]; ll dist[1234567]; priority_queue<pl> pq; void go(ll node){ used[node]=1; for(auto u:dog[node]){ for(int i=node+u,a=1;i<n;i+=u,a++){ if(dist[i] > dist[node] + a){ dist[i] = dist[node]+a; pq.push({-dist[i] , i}); } } for(int i=node-u,a=1;i>=0;i-=u,a++){ if(dist[i] > dist[node] + a){ dist[i] = dist[node]+a; pq.push({-dist[i] , i}); } } } } class A { public : static void funcA() { cin>>n>>m; ll st,en,b,p; cin>>st>>p; dog[st] . pb(p); cin>>en>>p; dog[en] . pb(p); m-=2; while(m--){ cin>>b>>p; dog[b].pb(p); } for(int i=0;i<=1e6;i++)dist[i]=MAX; pq.push({0,st}); dist[st]=0; while(pq.size()>0){ ll a = pq.top().ss; pq.pop(); if(a==en){ cout<<dist[en]; exit(0); } if(used[a]==0){ go(a); } } cout<<-1; } }lol; void solve() { A::funcA(); } int main() { ll T = 1; //cin>>T; boost; while (T--) { solve(); } }
#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...