أجهزة النقل الفوري

أجهزة النقل الفوري

الأولمبياد الوطني للبرمجة 2026 - المسابقة الثانية

الزمن المحدد: 0.5 ثانية
الذاكرة المحددة: 256 ميجابايت

يوجد \(N\) جهاز نقل فوري مصطفة في صف ومرقمة من \(1\) إلى \(N\). يرسلك كل جهاز إلى جهاز آخر.

أُعطيت مصفوفة \(a\) حجمها \(N\)، وتمثل \(a_i\) وجهة الجهاز \(i\). إذا دخلت الجهاز \(i\) تُنقل فورًا إلى الجهاز \(a_i\). لا يمكنك الحركة بنفسك؛ يمكنك فقط استخدام الجهاز في موقعك الحالي.

تبدأ من الجهاز \(S\)، وكل استخدام لجهاز يُحسب خطوة واحدة. حدد عدد الخطوات اللازمة للعودة إلى \(S\) أول مرة. إذا استحال ذلك فاطبع \(-1\).

المدخلات

يحتوي السطر الأول على \(N\) و\(S\)، حيث \(1 \le S \le N \le 2\cdot10^5\). ويحتوي السطر التالي على \(N\) عددًا \(a_1,a_2,\ldots,a_N\)، حيث \(1 \le a_i \le N\).

المخرجات

اطبع عدد الخطوات اللازمة للوصول إلى \(S\) مرة أخرى، أو \(-1\) إذا كان ذلك مستحيلًا.

التقييم

تُقيّم كل حالة اختبار بشكل مستقل، ودرجتك النهائية هي مجموع درجات جميع حالات الاختبار.

أمثلة

المدخلات

8 3
6 1 1 3 7 5 8 3

المخرجات

6

المدخلات

5 4
3 4 1 3 5

المخرجات

-1

ملاحظة

في المثال الأول نتبع المسار \(3\to1\to6\to5\to7\to8\to3\)، فنعود بعد ست خطوات. في المثال الثاني يصبح المسار \(4\to3\to1\to3\)، ثم تتكرر العقدتان \(3\) و\(1\) ولن نعود إلى \(4\).

الحل

اتبع المسار الوحيد الممكن وعلّم كل جهاز تزوره. إذا عدت إلى \(S\) فعدد الخطوات الحالي هو الإجابة. وإذا وصلت أولًا إلى جهاز آخر سبق زيارته فقد دخل المسار دورة لا تحتوي \(S\)، وتصبح العودة مستحيلة. التعقيد الزمني والذاكرة \(O(N)\).

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, s;
    cin >> n >> s;

    vector<int> destination(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> destination[i];
    }

    vector<bool> visited(n + 1, false);
    int current = s;
    int steps = 0;

    while (true) {
        if (visited[current]) {
            cout << -1 << '\n';
            return 0;
        }

        visited[current] = true;
        current = destination[current];
        steps++;

        if (current == s) {
            cout << steps << '\n';
            return 0;
        }
    }
}