Аой мен Битаро — JOI елінің Ұлттық ақпарат бюросына қарасты тыңшылар. Олардың бұл жолғы миссиясы — IOI еліне жасырын зерттеу жүргізу. Битаро IOI еліне жасырын кіреді, ал Аой JOI елінен Битароға нұсқаулар беріп отырады.

Жасырын кірер алдында Аой мен Битаро IOI елінің картасын алды. IOI елінде $0$-ден $N-1$-ге дейін нөмірленген $N$ қала бар. Сонымен қатар, IOI елінде $0$-ден $M-1$-ге дейін нөмірленген $M$ жол бар. $i$ жолы ($0\le i\le M-1$) $A_i$ қаласы мен $B_i$ қаласын екі бағытта байланыстырады, ал оның ұзындығы $C_i$-ге тең. Кейбір жолдармен жүріп өту арқылы кез келген екі қаланың арасында қатынауға болады. Битаро IOI еліндегі қалалар арасында осы жолдармен жүріп қозғалады.

Қосымша $Q$ зерттеу жоспары бар. $j$-ші жоспар ($0\le j\le Q-1$) IOI еліндегі $T_j$ қаласын зерттеуді қамтиды.

Жоғарыдағы барлық ақпарат алдымен Аойға да, Битароға да берілді. Содан кейін Битаро IOI еліне жасырын кіруге кірісті.

Битаро көптеген қуғыншылардан сәтті құтылып, жалдамалы өлтірушілерді жеңіп, ақырында IOI елінің $0$ қаласына жасырын кіре алды. Алайда, жасырын кіру операциясының өте қиын болғаны соншалық, Битаро IOI елі туралы кейбір ақпаратты жоғалтып алды. Нақтырақ айтқанда, Битаро $K$ жолдың, атап айтқанда $X_0,X_1,\ldots,X_{K-1}$ жолдарының ұзындығы туралы ақпаратты жоғалтып алды. Басқаша айтқанда, Битаро енді $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$ мәндерін білмейді. Битаро бұл ақпаратты жоғалтқанымен, Аойда ол әлі де сақталғанын ескеріңіз.

Битаро дереу Аойға қай жолдардың ұзындығы туралы ақпаратты жоғалтқанын хабарлады.

Миссияны орындау үшін Битаро $0$ қаласынан $Q$ зерттеу жоспарының нысанасы болып табылатын қалалардың әрқайсысына дейінгі ең қысқа жолды білгісі келеді.

Аой Битароға көмектесу үшін әр таңбасы 0 немесе 1 болатын жол (string) жібереді. Тосқауылға түсу қаупіне байланысты Аой Битароға жіберілетін мазмұнды барынша азайтқысы келеді.

IOI елі туралы ақпарат, зерттеу жоспарлары және Битаро ақпаратты жоғалтқан жолдар берілгенде, Аойдың Битароға жол жіберу стратегиясын жүзеге асыратын бағдарлама жазыңыз. Сондай-ақ, Битарода бар ақпарат пен Аой жіберген жол берілгенде, Битароның ең қысқа жолдарды табу стратегиясын жүзеге асыратын бағдарлама жазыңыз.

Іске асыру мәліметтері

Сіз 2 файл жіберуіңіз керек.

Бірінші файл — Aoi.cpp. Бұл файл Аойдың стратегиясын іске асыруға арналған және келесі функцияларды іске асыруы тиіс. Бағдарлама #include препроцессор директивасын қолданып Aoi.h файлын қосуы керек.

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 параметрі — Битаро ұзындығы туралы ақпаратты жоғалтқан жолдар саны, $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$ болатын массив. Ол Битароның X[0], X[1], ..., X[K-1] жолдарының ұзындығы туралы ақпаратты жоғалтқанын көрсетеді.
• Қайтарылатын мән — Аойдың Битароға жіберетін $s$ жолы.
• $s$ жолының әрбір таңбасы 0 немесе 1 болуы керек. Егер бұл шарт орындалмаса, бағдарламаңыз Wrong Answer [1] деп бағаланады.
• $s$ жолының ұзындығы ең көп дегенде $12\,000$ болуы керек. Егер бұл шарт орындалмаса, бағдарламаңыз Wrong Answer [2] деп бағаланады.

Екінші файл — Bitaro.cpp. Бұл файл Битароның стратегиясын іске асыруға арналған және келесі функцияларды іске асыруы тиіс. Бағдарлама #include препроцессор директивасын қолданып Bitaro.h файлын қосуы керек.

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 параметрі — Битаро ұзындығы туралы ақпаратты жоғалтқан жолдар саны, $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$ болатын массив. Ол Битароның X[0], X[1], ..., X[K-1] жолдарының ұзындығы туралы ақпаратты жоғалтқанын көрсетеді.
• s аргументі — әр таңбасы 0 немесе 1 болатын, Аойдың Битароға жіберген жолын білдіретін жол.

Bitaro.cpp ішінде бағдарламаңыз келесі функцияны шақыра алады.

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

Бұл функцияға $(j+1)$-ші рет шақыру кезінде ($0\le j\le Q-1$), сіз $j$-ші зерттеу жоспарының нысанасы болып табылатын $0$ қаласынан $T_j$ қаласына дейінгі ең қысқа жолды жауап ретінде беруіңіз керек.

• e параметрі — $0$ қаласынан $T_j$ қаласына дейінгі ең қысқа жолды білдіретін массив.
• e массивінің ұзындығы $n$ болсын. 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$ рет шақырылуы керек. Егер bitaro функциясының орындалуы соңында answer функциясын шақыру саны $Q$-ға тең болмаса, бағдарламаңыз Wrong Answer [6] деп бағаланады.

Маңызды ескертпелер

• Бағдарламаңыз ішкі пайдалану үшін басқа функцияларды іске асыра алады немесе жаһандық айнымалыларды (global variables) пайдалана алады. Жіберілген файлдар грейдермен бірге компиляцияланып, біртұтас орындалатын файлға айналады. Басқа файлдармен қақтығысты болдырмау үшін барлық жаһандық айнымалылар мен ішкі функциялар атаусыз атаулар кеңістігінде (unnamed namespace) жариялануы керек. Бағалау кезінде ол Аой және Битаро болып екі процесс ретінде орындалады. Аой процесі мен Битаро процесі жаһандық айнымалыларды ортақ пайдалана алмайды.
• Бағдарламаңыз стандартты кірісті және стандартты шығысты пайдаланбауы керек. Бағдарламаңыз басқа файлдармен ешқандай әдіспен байланыспауы тиіс. Дегенмен, бағдарламаңыз стандартты қате шығысына (standard error) жөндеу (debugging) ақпаратын шығара алады.

Компиляция және сынақ ретінде іске қосу

Бағдарламаңызды тексеру үшін жарыс веб-бетінен үлгі грейдері бар архив файлын жүктеп алуға болады. Архив файлында бағдарламаңыздың үлгі бастапқы файлы да бар.

Үлгі грейдер — 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{gathered} 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{gathered} $$

Үлгі грейдердің шығыс деректері

Үлгі грейдер стандартты шығыс пен стандартты қате шығысына келесі ақпаратты шығарады (анықтық үшін тырнақшаға алынған).

• Егер бағдарламаңыз Wrong Answer [1], [2], [3], [4] немесе [6] деп бағаланса, үлгі грейдер оның түрін стандартты қате шығысына Wrong Answer [1] сияқты жазады. Стандартты шығысқа ештеңе шығарылмайды.
• Олай болмаса, aoi функциясынан қайтарылған $s$ жолының ұзындығы стандартты қате шығысына Accepted: 2024 форматында шығарылады. Сонымен қатар, answer функциясына $(j+1)$-ші шақырудағы ($0\le j\le Q-1$) жолдың ұзындығы стандартты шығыстың $(j+1)$-ші жолына шығарылады. Үлгі бағалау бағдарламасы жолдың ең қысқа екенін тексермейді.

Егер бағдарламаңыз Wrong Answer-дің бірнеше түрінің шарттарына сәйкес келсе, үлгі грейдер олардың тек біреуін ғана хабарлайды.

Шектеулер

Барлық кіріс деректері келесі шарттарды қанағаттандырады:

• $2\le N\le10\,000$.
• $1\le M\le20\,000$.
• $1\le Q\le16$.
• $1\le K\le300$.
• $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\le10^{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$ ұпай.

Әйтпесе, бағалау осы тапсырманың барлық тест жағдайлары бойынша aoi функциясынан қайтарылған $s$ жолының $L$ деп белгіленген ең үлкен ұзындығына негізделеді.

• Егер $1561\le L\le12\,000$ болса, ұпай саны — $\left\lfloor\dfrac{100\,000}{L-560}\right\rfloor$ ұпай.
• Егер $0\le L\le1560$ болса, ұпай саны — $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 файлдарын үлгі грейдер үшін кіріс ретінде пайдалануға болады.