Aoi ו־Bitaro הם מרגלים המשתייכים ללשכת המידע הלאומית של מדינת JOI. משימתם הפעם היא לערוך חקירה סמויה במדינת IOI. Bitaro מסתנן למדינת IOI, ואילו Aoi נותנת לו הוראות ממדינת JOI.

לפני ההסתננות השיגו Aoi ו־Bitaro מפה של מדינת IOI. במדינת 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. אולם, בשל הקושי הרב של מבצע ההסתננות, איבד Bitaro חלק מהמידע על מדינת IOI. בפרט, הוא איבד את המידע על אורכיהם של $K$ כבישים, שהם $X_0,X_1,\ldots,X_{K-1}$. במילים אחרות, Bitaro אינו יודע עוד את הערכים $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. שימו לב שאף ש־Bitaro איבד מידע זה, הוא עדיין מצוי בידי Aoi.

Bitaro דיווח מיד ל־Aoi על אילו כבישים איבד את מידע האורך.

כדי להשלים את המשימה, Bitaro רוצה לדעת מסלול קצר ביותר מהעיר $0$ לכל אחת מערי היעד של $Q$ תוכניות החקירה.

Aoi תשלח ל־Bitaro מחרוזת שכל תו בה הוא 0 או 1, כדי לסייע לו. בשל סכנת היירוט, Aoi רוצה למזער את התוכן הנשלח ל־Bitaro.

כתבו תוכנית המממשת את האסטרטגיה של Aoi לשליחת מחרוזת ל־Bitaro, בהינתן המידע על מדינת IOI, תוכניות החקירה והכבישים שעליהם איבד Bitaro מידע. בנוסף, כתבו תוכנית המממשת את האסטרטגיה של Bitaro למציאת המסלולים הקצרים ביותר, בהינתן המידע שברשותו והמחרוזת ששלחה Aoi.

פרטי מימוש

עליכם להגיש 2 קבצים.

הקובץ הראשון הוא 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$ הוא מספר הערים $N$ במדינת IOI.
• הפרמטר $M$ הוא מספר הכבישים $M$ במדינת IOI.
• הפרמטר $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$ הוא מספר הערים $N$ במדינת IOI.
• הפרמטר $M$ הוא מספר הכבישים $M$ במדינת IOI.
• הפרמטר $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$ פעמים. אם מספר הקריאות לפונקציה answer אינו שווה ל־$Q$ בסיום ביצוע הפונקציה bitaro, התוכנית תישפט כ־Wrong Answer [6].

הערות חשובות

• התוכנית יכולה לממש פונקציות נוספות לשימוש פנימי או להשתמש במשתנים גלובליים. הקבצים המוגשים יקומפלו יחד עם תוכנית הבדיקה לקובץ הרצה אחד. יש להצהיר על כל המשתנים הגלובליים והפונקציות הפנימיות בתוך מרחב שמות ללא שם, כדי להימנע מהתנגשויות עם קבצים אחרים. בזמן השיפוט יופעלו שני תהליכים, של Aoi ושל Bitaro. התהליך של 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.

שימו לב שתוכנית הבדיקה האמיתית שונה מתוכנית הבדיקה לדוגמה. תוכנית הבדיקה לדוגמה תרוץ כתהליך יחיד, שיקרא נתוני קלט מהקלט הסטנדרטי ויכתוב את התוצאות לפלט הסטנדרטי ולפלט השגיאות הסטנדרטי.

הקלט של תוכנית הבדיקה לדוגמה

תוכנית הבדיקה לדוגמה קוראת את הנתונים הבאים מהקלט הסטנדרטי.

N M
A_0 B_0 C_0
A_1 B_1 C_1
...
A_{M-1} B_{M-1} C_{M-1}
Q
T_0 T_1 ... T_{Q-1}
K
X_0 X_1 ... X_{K-1}

הפלט של תוכנית הבדיקה לדוגמה

תוכנית הבדיקה לדוגמה מדפיסה את המידע הבא לפלט הסטנדרטי ולפלט השגיאות הסטנדרטי (המירכאות נועדו להבהרה).

• אם התוכנית נשפטת כ־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 בדוגמה זו, גם הקריאה answer([2]) מתקבלת.

הקובץ sample-01-in.txt, שאפשר להוריד מאתר התחרות, מתאים לקלט לדוגמה 1.

אפשר להשתמש בקבצים sample-01-in.txt ו־sample-02-in.txt, הכלולים בקבצים להורדה מאתר התחרות, כקלט לתוכנית הבדיקה לדוגמה.