# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
45932 | TheDarkning | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 1083 ms | 7156 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
▄█▀ ▀█▀ ▄▀▄ █▀ █▄█▄█ ▄▀▄ █▀ ▄█▀
<⇋⇋⇋⋛∰≓⊂(⌒,_ゝ⌒)⊃≓∰⋛⇋⇋⇋>
♔♕♖♗♘♙ ☜❷☞✪ ィℋ६ ≈ ᗫẵℜℵĬŊĞ ✪☜❷☞ ♚♛♜♝♞♟
♔♕♖♗♘♙ ♚♛♜♝♞♟
˙·٠•●♥ Ƹ̵̡Ӝ̵̨̄Ʒ ♥●•٠·˙
**/
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <map>
#include <deque>
#include <string>
#include <memory.h>
#include <queue>
#include <set>
#include <assert.h>
#define sz(s) s.size()
#define pb push_back
#define fr first
#define sc second
#define mk make_pair
#define all(s) s.begin(), s.end()
using namespace std;
const int N = 2e5 + 5;
const int inf = 1e9 + 7;
vector < int > w[N];
priority_queue < pair < int, int > > q;
int n, m, p, b, x, s, cnt;
int d[N];
main()
{
scanf("%d%d", &n, &m);
for( int i = 1; i <= m; i++ )
{
scanf("%d%d", &p, &b);
p++;
if( i == 1 )
s = p;
if( i == 2 )
x = p;
w[ p ].pb( b );
}
for (int i = 1; i <= n; i ++) {
sort (w[i].begin(),w[i].end());
w[i].erase(unique(w[i].begin(),w[i].end()),w[i].end());
}
for (int i = 1; i <= n; i ++)
d[i] = inf;
d[ s ] = 0;
q.push( mk( d[s], s ) );
while( !q.empty() )
{
int v = q.top().sc, cur = -q.top().fr;
q.pop();
if( cur > d[ v ] ) continue;
if (v == x) {
printf("%d", d[v]);
return 0;
}
for(int j = 0; j < w[v].size(); j ++)
{
int l = w[v][j];
int to = v;
cnt = 0;
while( to <= n )
{
cnt++;
to = v + l * cnt;
if( to > n ) break;
if( d[ v ] + cnt < d[ to ] )
{
d[ to ] = d[ v ] + cnt;
q.push( mk( -d[ to ], to ) );
}
}
to = v;
cnt = 0;
while( to )
{
cnt++;
to = v - l * cnt;
if( to <= 0 ) break;
if( d[ v ] + cnt < d[ to ] )
{
d[ to ] = d[ v ] + cnt;
q.push( mk( -d[ to ], to ) );
}
}
}
}
if( d[ x ] == inf )
d[ x ] = -1;
printf("%d", d[x]);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |