結果
問題 | No.1868 Teleporting Cyanmond |
ユーザー |
![]() |
提出日時 | 2022-03-11 21:22:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 63 ms / 2,000 ms |
コード長 | 881 bytes |
コンパイル時間 | 2,208 ms |
コンパイル使用メモリ | 204,664 KB |
最終ジャッジ日時 | 2025-01-28 08:04:49 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int N; cin >> N; vector<int> R(N - 1); for (int i = 0; i < N - 1; i++){ cin >> R[i]; R[i]--; } vector<vector<pair<int, int>>> E(N); for (int i = 0; i < N - 1; i++){ E[i + 1].push_back(make_pair(0, i)); } for (int i = 0; i < N - 1; i++){ E[i].push_back(make_pair(1, R[i])); } vector<int> d(N, -1); deque<pair<int, int>> dq; dq.push_back(make_pair(0, 0)); while (!dq.empty()){ int c = dq.front().first; int v = dq.front().second; dq.pop_front(); if (d[v] == -1){ d[v] = c; for (auto P : E[v]){ int w = P.second; if (d[w] == -1){ if (P.first == 0){ dq.push_front(make_pair(c, w)); } else { dq.push_back(make_pair(c + 1, w)); } } } } } cout << d[N - 1] << endl; }