Aoi وBitaro جاسوسان تابعان لمكتب المعلومات الوطني في دولة JOI. مهمتهما هذه المرة هي إجراء تحقيق سري داخل دولة IOI. يتسلل Bitaro إلى دولة IOI، بينما ترسل Aoi إليه التعليمات من دولة JOI.

قبل التسلل، حصل الاثنان على خريطة لدولة IOI. فيها $N$ مدن مرقمة من $0$ إلى $N-1$، وكذلك $M$ طرق مرقمة من $0$ إلى $M-1$. يربط الطريق $i$ ($0\le i\le M-1$) المدينتين $A_i$ و$B_i$ في الاتجاهين، وطوله $C_i$. يمكن التنقل بين أي مدينتين باستخدام بعض الطرق. يتنقل Bitaro بين مدن دولة IOI باستخدام هذه الطرق.

توجد أيضًا $Q$ خطط تحقيق. تتضمن الخطة $j$ ($0\le j\le Q-1$) التحقيق في المدينة $T_j$ في دولة IOI.

أُعطيت جميع المعلومات السابقة لكل من Aoi وBitaro أولًا. ثم بدأ Bitaro عملية التسلل إلى دولة IOI.

نجح Bitaro في الإفلات من مطاردين كثيرين، وهزم القتلة، وتمكن أخيرًا من التسلل إلى المدينة $0$ في دولة IOI. لكن بسبب الصعوبة البالغة للعملية، فقد بعض المعلومات عن الدولة. تحديدًا، فقد معلومات أطوال $K$ طرق، هي $X_0,X_1,\ldots,X_{K-1}$. أي إنه لم يعد يعرف قيم $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. لاحظ أن Aoi ما زالت تحتفظ بهذه المعلومات رغم أن Bitaro فقدها.

أبلغ Bitaro فورًا Aoi بالطرق التي فقد معلومات أطوالها.

لإنجاز المهمة، يريد Bitaro معرفة مسار أقصر من المدينة $0$ إلى كل مدينة تستهدفها خطط التحقيق الـ $Q$.

سترسل Aoi إلى Bitaro سلسلة كل محرف فيها إما ‘0’ أو ‘1’ لمساعدته. وبسبب خطر اعتراض الرسالة، تريد تقليل المحتوى المرسل إليه قدر الإمكان.

اكتب برنامجًا ينفذ استراتيجية Aoi لإرسال سلسلة إلى Bitaro، عند إعطائه معلومات دولة IOI وخطط التحقيق والطرق التي فقد Bitaro معلوماتها. واكتب أيضًا برنامجًا ينفذ استراتيجية Bitaro لإيجاد أقصر المسارات، باستخدام المعلومات التي يملكها والسلسلة المرسلة من Aoi.

تفاصيل التنفيذ

يجب تقديم ملفين.

الملف الأول هو Aoi.cpp. ينفذ استراتيجية Aoi، ويجب أن ينفذ الدالة التالية. يجب تضمين Aoi.h باستخدام توجيه المعالج المسبق #include.

• std::string aoi(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> C, std::vector<int> T, std::vector<int> X)

  تُستدعى هذه الدالة مرة واحدة فقط لكل حالة اختبار.

  • المعامل N هو عدد مدن مملكة IOI، وهو $N$.
  • المعامل M هو عدد طرق مملكة IOI، وهو $M$.
  • المعامل Q هو عدد خطط التحقيق $Q$.
  • المعامل K هو عدد الطرق التي فقد Bitaro معلومات أطوالها، ويُرمز إليه بـ $K$.
  • المعاملات A وB وC مصفوفات طولها $M$. تعني أن الطريق $i$ ($0\le i\le M-1$) يربط المدينتين A[i] وB[i] في الاتجاهين، وطوله C[i].
  • المعامل T مصفوفة طولها $Q$. تعني أن الخطة $j$ ($0\le j\le Q-1$) تتضمن التحقيق في المدينة T[j].
  • المعامل X مصفوفة طولها $K$. يحدد أن Bitaro فقد معلومات أطوال الطرق X[0] وX[1] و… وX[K-1].
  • القيمة المعادة هي السلسلة $s$ التي ترسلها Aoi إلى Bitaro.
  • يجب أن يكون كل محرف في $s$ إما ‘0’ أو ‘1’. وإلا يُحكم على البرنامج بـ Wrong Answer [1].
  • يجب ألا يزيد طول $s$ على $12\,000$. وإلا يُحكم على البرنامج بـ Wrong Answer [2].

الملف الثاني هو Bitaro.cpp. ينفذ استراتيجية Bitaro، ويجب أن ينفذ الدالة التالية. يجب تضمين Bitaro.h باستخدام توجيه المعالج المسبق #include.

• void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> C, std::vector<int> T, std::vector<int> X, std::string s)

  تُستدعى هذه الدالة مرة واحدة فقط بعد استدعاء aoi.

  • المعامل N هو عدد مدن مملكة IOI، وهو $N$.
  • المعامل M هو عدد طرق مملكة IOI، وهو $M$.
  • المعامل Q هو عدد خطط التحقيق $Q$.
  • المعامل K هو عدد الطرق التي فقد Bitaro معلومات أطوالها، ويُرمز إليه بـ $K$.
  • المعاملات A وB وC مصفوفات طولها $M$. تعني أن الطريق $i$ ($0\le i\le M-1$) يربط المدينتين A[i] وB[i] في الاتجاهين، وطوله C[i].
  • المعامل T مصفوفة طولها $Q$. تعني أن الخطة $j$ ($0\le j\le Q-1$) تتضمن التحقيق في المدينة T[j].
  • المعامل X مصفوفة طولها $K$. يحدد أن Bitaro فقد معلومات أطوال الطرق X[0] وX[1] و… وX[K-1].
  • الوسيط s سلسلة كل محرف فيها إما ‘0’ أو ‘1’، وتمثل السلسلة المرسلة من Aoi إلى Bitaro.

يمكن للبرنامج داخل Bitaro.cpp استدعاء الدالة التالية.

• void answer(const std::vector<int> &e)

  في الاستدعاء رقم $(j+1)$ ($0\le j\le Q-1$)، يجب أن تقدم أقصر مسار من المدينة $0$ إلى المدينة $T_j$، هدف خطة التحقيق $j$.

  • المعامل e مصفوفة تمثل أقصر مسار من المدينة $0$ إلى المدينة $T_j$.
  • ليكن $n$ طول المصفوفة e. العناصر e[0] وe[1] و… وe[n-1] هي أرقام الطرق في أقصر مسار من المدينة $0$ إلى المدينة $T_j$، بترتيب عبورها.
  • إذا وجدت عدة مسارات أقصر، يمكن اختيار أي منها للإجابة.
  • يجب أن يقع كل عنصر في e بين $0$ و$M-1$. وإلا يُحكم على البرنامج بـ Wrong Answer [3].

  • يجب أن تشكل سلسلة الطرق التي يحددها الوسيط e مسارًا من المدينة $0$ إلى المدينة $T_j$. وبصورة أدق، يجب أن تتحقق الشروط التالية.

    توجد سلسلة أعداد $u_0,u_1,\ldots,u_n$ بحيث:

    • $u_0=0$.
    • $u_n=T_j$.
    • يربط الطريق e[k]، حيث $0\le k\le n-1$، المدينتين $u_k$ و$u_{k+1}$.

    إذا لم تتحقق هذه الشروط، يُحكم على البرنامج بـ Wrong Answer [4].

  • إذا لم تكن سلسلة الطرق التي يحددها e أقصر مسار من المدينة $0$ إلى المدينة $T_j$ بين جميع المسارات التي تبدأ في $0$ وتنتهي في $T_j$، يُحكم على البرنامج بـ Wrong Answer [5]. يُعرَّف طول المسار بأنه مجموع أطوال الطرق المستخدمة.

  • يجب استدعاء answer بالضبط $Q$ مرات. إذا لم يكن عدد استدعاءاتها مساويًا لـ $Q$ عند انتهاء تنفيذ bitaro، يُحكم على البرنامج بـ Wrong Answer [6].

تنبيهات مهمة

• يمكن للبرنامج تنفيذ دوال أخرى للاستخدام الداخلي، أو استخدام متغيرات عامة. تُجمَّع الملفات المقدمة مع برنامج التقييم لتشكيل ملف تنفيذي واحد. ينبغي التصريح بجميع المتغيرات العامة والدوال الداخلية داخل نطاق أسماء غير مسمى لتجنب التعارض مع الملفات الأخرى. عند التقييم، يُنفذ البرنامج في عمليتين، واحدة لـ Aoi وأخرى لـ Bitaro. لا يمكن للعملتين مشاركة المتغيرات العامة.
• يجب ألا يستخدم البرنامج الإدخال القياسي أو الإخراج القياسي، وألا يتواصل مع ملفات أخرى بأي وسيلة. لكن يمكنه إخراج معلومات التنقيح إلى مخرج الخطأ القياسي.

التجميع والتشغيل التجريبي

يمكن تنزيل ملف أرشيف من موقع المسابقة، يتضمن برنامج تقييم نموذجيًا لاختبار برنامجك. ويتضمن الأرشيف أيضًا ملف مصدر نموذجيًا لبرنامجك.

برنامج التقييم النموذجي هو grader.cpp. لاختبار برنامجك، ضع grader.cpp وAoi.cpp وBitaro.cpp وAoi.h وBitaro.h في المجلد نفسه، ونفذ الأمر التالي للتجميع. ويمكن بدلًا من ذلك تشغيل compile.sh الموجود في الأرشيف.

g++ -std=gnu++20 -O2 -o grader grader.cpp Aoi.cpp Bitaro.cpp

عند نجاح التجميع، يُنشأ الملف التنفيذي grader.

لاحظ أن برنامج التقييم الفعلي يختلف عن النموذجي. يعمل النموذجي في عملية واحدة، ويقرأ البيانات من الإدخال القياسي ويكتب النتائج إلى الإخراج القياسي ومخرج الخطأ القياسي.

الإدخال لبرنامج التقييم النموذجي

يقرأ برنامج التقييم النموذجي البيانات التالية من الإدخال القياسي.

$$ \begin{array}{lll} N&M\\ A_0&B_0&C_0\\ A_1&B_1&C_1\\ \vdots\\ A_{M-1}&B_{M-1}&C_{M-1}\\ Q\\ T_0&T_1\ \ldots\ T_{Q-1}\\ K\\ X_0&X_1\ \ldots\ X_{K-1} \end{array} $$

الإخراج لبرنامج التقييم النموذجي

يكتب برنامج التقييم النموذجي المعلومات التالية إلى الإخراج القياسي ومخرج الخطأ القياسي (علامات الاقتباس للتوضيح).

• إذا حُكم على البرنامج بـ Wrong Answer [1] أو [2] أو [3] أو [4] أو [6]، يكتب برنامج التقييم نوع الخطأ، مثل “Wrong Answer [1]”، إلى مخرج الخطأ القياسي. ولا يكتب شيئًا إلى الإخراج القياسي.
• وإلا، يُكتب طول السلسلة $s$ المعادة من aoi إلى مخرج الخطأ القياسي بالصيغة “Accepted: 2024”. كذلك يُكتب طول المسار في الاستدعاء رقم $(j+1)$ ($0\le j\le Q-1$) للدالة answer إلى السطر رقم $(j+1)$ من الإخراج القياسي. برنامج التقييم النموذجي لا يتحقق من كون المسار أقصر مسار.

إذا حقق البرنامج شروط عدة أنواع من Wrong Answer، فلا يبلغ برنامج التقييم النموذجي إلا عن واحد منها.

القيود

تحقق جميع بيانات الإدخال الشروط التالية:

• $2\le N\le 10\,000$.
• $1\le M\le 20\,000$.
• $1\le Q\le 16$.
• $1\le K\le 300$.
• $0\le A_i<B_i\le N-1$ ($0\le i\le M-1$).
• $(A_i,B_i)\ne(A_j,B_j)$ ($0\le i<j\le M-1$).
• $1\le C_i\le 10^{12}$ ($0\le i\le M-1$).
• $1\le T_j\le N-1$ ($0\le j\le Q-1$).
• $T_j\ne T_k$ ($0\le j<k\le Q-1$).
• $0\le X_k\le M-1$ ($0\le k\le K-1$).
• $X_k\ne X_l$ ($0\le k<l\le K-1$).
• يمكن السفر من أي مدينة إلى أي مدينة أخرى باستخدام بعض الطرق.
• جميع قيم الإدخال أعداد صحيحة.

المهام الفرعية

إذا حُكم على البرنامج بأي نوع من Wrong Answer [1]–[6] (انظر «تفاصيل التنفيذ») أو حدث أي خطأ أثناء التشغيل (TLE (تجاوز حد الزمن)، أو MLE (تجاوز حد الذاكرة)، أو انتهاء غير طبيعي، وما شابه) في أي حالة اختبار، فالدرجة $0$ نقطة.

وإلا، تُحسب الدرجة بناءً على أكبر طول للسلسلة $s$ المعادة من aoi عبر جميع حالات اختبار هذه المسألة، ونرمز إليه بـ $L$.

• إذا كان $1561\le L\le 12\,000$، فالدرجة $\left\lfloor\dfrac{100\,000}{L-560}\right\rfloor$ نقطة.
• إذا كان $0\le L\le 1560$، فالدرجة $100$ نقطة.

هنا، تمثل $\lfloor x\rfloor$ أكبر عدد صحيح لا يتجاوز $x$.

أمثلة

فيما يلي إدخال نموذجي لبرنامج التقييم النموذجي واستدعاءات الدوال المقابلة له.

الإدخال 1

3 3
1 2 1
0 2 2
0 1 3
2
2 1
2
0 1

استدعاءات الدوال النموذجية

ملاحظة

يمكن الحصول على أقصر مسار من المدينة $0$ إلى المدينة $1$ إما بعبور الطريقين $1$ ثم $0$ بهذا الترتيب، أو بعبور الطريق $2$ وحده. لذلك يُقبل أيضًا الاستدعاء answer([2]) بدل الاستدعاء الثاني للدالة answer في هذا المثال.

الملف sample-01-in.txt المتاح للتنزيل من موقع المسابقة يطابق مثال الإدخال 1.

يمكن استخدام الملفين sample-01-in.txt وsample-02-in.txt ضمن الملفات القابلة للتنزيل من موقع المسابقة كإدخال لبرنامج التقييم النموذجي.