Submission #671072

#TimeUsernameProblemLanguageResultExecution timeMemory
671072pls33Fire drill (LMIO18_sauga)C++17
88.85 / 100
1043 ms5728 KiB
// Oficialus uždavinio 'sauga-vyr' (2018 m. LMIO finalinis etapas) sprendimas. // eik nx su savo np complete uzduotimis #include <bits/stdc++.h> using namespace std; const int MAX_N = 1000; const int APEJIMU_KIEKIS = 145; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); struct Pastatas { vector<int> ankstesni; // Sąrašas pastatų, kuriuos reikia evakuoti anksčiau. Užpildomas nuskaitant // duomenis ir daugiau nebeatnaujinamas. vector<int> velesni; // Sąrašas pastatų, kuriuos reikia evakuoti vėliau. Užpildomas nuskaitant // duomenis ir daugiau nebeatnaujinamas. int n_ankstesni, n_velesni; // Vykstant evakuacijai šie kintamieji bus atnaujinami. Jie nurodo, kiek dar // liko pastatų, kuriuos reikia evakuoti anskčiau/vėliau. bool evakuotas; // Nurodo ar pastatas jau evakuotas. } pastatai[MAX_N]; vector<int> evakuojami_prasizengiant; // Bus evakuojami patys pirmieji. vector<int> evakuojami_pradzioje; // Bus evakuojami per vidurį. vector<int> evakuojami_pabaigoje; // Bus evakuojami patys paskutiniai. vector<int> like_pastatai; // Nuolatos atnaujinamas sąrašas pastatų, kuriuos dar reikia evakuoti. int n_aplankymai[MAX_N]; // Šį masyvą naudosime skaičiavimuose. Jis nurodo, kaip dažnai pastatai // aplankomi kryptiniu grafu vaikštant atsitiktinai. int N, riba; void Nuskaityti() { scanf("%*d%d%d", &N, &riba); // Testo numeris šiam sprendimui nesvarbus. for (int i = 0; i < N; ++i) { like_pastatai.push_back(i); scanf("%d", &pastatai[i].n_ankstesni); for (int j = 0; j < pastatai[i].n_ankstesni; ++j) { int k; scanf("%d", &k); pastatai[i].ankstesni.push_back(k - 1); pastatai[k - 1].velesni.push_back(i); ++pastatai[k - 1].n_velesni; } } } void Spausdinti() { for (int i = 0; i < evakuojami_prasizengiant.size(); ++i) printf("%d\n", evakuojami_prasizengiant[i] + 1); for (int i = 0; i < evakuojami_pradzioje.size(); ++i) printf("%d\n", evakuojami_pradzioje[i] + 1); for (int i = evakuojami_pabaigoje.size() - 1; i >= 0; --i) printf("%d\n", evakuojami_pabaigoje[i] + 1); } void PerziuretiLikusiusPastatus() // Išmeta ką tik evakuotus pastatus iš likusių pastatų sąrašo. { for (int i = 0; i < like_pastatai.size();) if (pastatai[like_pastatai[i]].evakuotas) { like_pastatai[i] = like_pastatai[like_pastatai.size() - 1]; like_pastatai.pop_back(); } else { ++i; } } void EvakuotiPastata(int i, vector<int> &prioritetas) // Evakuoja pastatą ir sumažina išeinančių ir įeinančių rodyklių skaičių (t.y. // kintamuosius n_ankstesni ir n_velesni) kaimyniniams pastatams. Automatiškai // evakuoja kaimynus, kurie nebeturi įeinančių arba išeinančių rodyklių. { pastatai[i].evakuotas = true; prioritetas.push_back(i); for (int j = 0; j < pastatai[i].ankstesni.size(); ++j) { int ankstesnis = pastatai[i].ankstesni[j]; if (!pastatai[ankstesnis].evakuotas && !(--pastatai[ankstesnis].n_velesni)) EvakuotiPastata(ankstesnis, evakuojami_pabaigoje); } for (int j = 0; j < pastatai[i].velesni.size(); ++j) { int velesnis = pastatai[i].velesni[j]; if (!pastatai[velesnis].evakuotas && !(--pastatai[velesnis].n_ankstesni)) EvakuotiPastata(velesnis, evakuojami_pradzioje); } } void NuskabytiNesvarbius() // Evakuoja pastatus, kurie neturi įeinančių ar išeinančių rodyklių. { for (int i = 0; i < N; ++i) { if (!pastatai[i].evakuotas && !pastatai[i].n_ankstesni) EvakuotiPastata(i, evakuojami_pradzioje); else if (!pastatai[i].evakuotas && !pastatai[i].n_velesni) EvakuotiPastata(i, evakuojami_pabaigoje); } } int PasirinktiIsejima(int i) // Naudojama atsitiktinai vaikštant kryptiniu grafu. Pasirenka atsitiktinę // išeinančią rodyklę iš pastato. { while (1) { int r = rng() % pastatai[i].velesni.size(); int kandidatas = pastatai[i].velesni[r]; if (pastatai[kandidatas].evakuotas) { pastatai[i].velesni[r] = pastatai[i].velesni[pastatai[i].velesni.size() - 1]; pastatai[i].velesni.pop_back(); } else { return kandidatas; } } } int RastiSvarbiausiaPastata() // Pasirenka pastatą, kuris dažniausiai aplankomas atsitiktinai vaišktant // kryptiniu grafu. { for (int i = 0; i < like_pastatai.size(); ++i) n_aplankymai[like_pastatai[i]] = 0; int dabar_lankomas = like_pastatai[rng() % like_pastatai.size()]; int dazniausiai_lankomas = dabar_lankomas; n_aplankymai[dabar_lankomas] = 1; for (int t = 0; t < like_pastatai.size() * APEJIMU_KIEKIS; ++t) { dabar_lankomas = PasirinktiIsejima(dabar_lankomas); if (++n_aplankymai[dabar_lankomas] > n_aplankymai[dazniausiai_lankomas]) dazniausiai_lankomas = dabar_lankomas; } return dazniausiai_lankomas; } void PaliktiMaziausiaiTrukdanti() // Funkcija naudojamas tada, kai be pražangos pavyksta evakuoti tik labai // nedidelį kiekį pastatų. Ji pasirenka pastatą su mažiausiu kiekiu įeinančių // arba išeinančių rodyklių ir su pražangomis evakuoja jo kaimynus. { int maziausiai_ankstesniu = like_pastatai[0]; int maziausiai_velesniu = like_pastatai[0]; for (int i = 0; i < like_pastatai.size(); ++i) { int kandidatas = like_pastatai[i]; if (pastatai[kandidatas].n_ankstesni < pastatai[maziausiai_ankstesniu].n_ankstesni) maziausiai_ankstesniu = kandidatas; if (pastatai[kandidatas].n_velesni < pastatai[maziausiai_velesniu].n_velesni) maziausiai_velesniu = kandidatas; } if (pastatai[maziausiai_ankstesniu].n_ankstesni < pastatai[maziausiai_velesniu].n_velesni) { for (int j = 0; j < pastatai[maziausiai_ankstesniu].ankstesni.size(); ++j) if (!pastatai[pastatai[maziausiai_ankstesniu].ankstesni[j]].evakuotas) EvakuotiPastata(pastatai[maziausiai_ankstesniu].ankstesni[j], evakuojami_prasizengiant); } else { for (int j = 0; j < pastatai[maziausiai_velesniu].velesni.size(); ++j) if (!pastatai[pastatai[maziausiai_velesniu].velesni[j]].evakuotas) EvakuotiPastata(pastatai[maziausiai_velesniu].velesni[j], evakuojami_prasizengiant); } } int main() { Nuskaityti(); NuskabytiNesvarbius(); PerziuretiLikusiusPastatus(); if (riba < N - 30) { // Šis atvejis pilnai išsprendžia 9 testus iš 10. while (!like_pastatai.empty()) { EvakuotiPastata(RastiSvarbiausiaPastata(), evakuojami_prasizengiant); PerziuretiLikusiusPastatus(); } } else { // Reikalingas tik vienam testui. while (!like_pastatai.empty()) { PaliktiMaziausiaiTrukdanti(); PerziuretiLikusiusPastatus(); } } Spausdinti(); return 0; }

Compilation message (stderr)

sauga.cpp: In function 'void Spausdinti()':
sauga.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < evakuojami_prasizengiant.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < evakuojami_pradzioje.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'void PerziuretiLikusiusPastatus()':
sauga.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < like_pastatai.size();)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'void EvakuotiPastata(int, std::vector<int>&)':
sauga.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (int j = 0; j < pastatai[i].ankstesni.size(); ++j)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int j = 0; j < pastatai[i].velesni.size(); ++j)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'int RastiSvarbiausiaPastata()':
sauga.cpp:146:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for (int i = 0; i < like_pastatai.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:153:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for (int t = 0; t < like_pastatai.size() * APEJIMU_KIEKIS; ++t)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'void PaliktiMaziausiaiTrukdanti()':
sauga.cpp:171:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |     for (int i = 0; i < like_pastatai.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:182:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |         for (int j = 0; j < pastatai[maziausiai_ankstesniu].ankstesni.size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:188:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |         for (int j = 0; j < pastatai[maziausiai_velesniu].velesni.size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'void Nuskaityti()':
sauga.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%*d%d%d", &N, &riba); // Testo numeris šiam sprendimui nesvarbus.
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%d", &pastatai[i].n_ankstesni);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |             scanf("%d", &k);
      |             ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...