// Oficialus uždavinio 'sauga-vyr' (2018 m. LMIO finalinis etapas) sprendimas.
//
// Šis algoritmas buvo naudojamas generuojant atsakymus testams.
// Dėl to, kad skirtingose sistemose pseudoatsitiktiniai skaičiai gali būti
// generuojami šiek tiek kitaip, rezultatai gali truputį skirtis (kai kurie
// testai gali būti išsprendžiami šiek tiek geriau, kiti - šiek tiek blogiau).
// Norint surinkti visus taškus, gali reikti išbandyti keletą atsitiktinių
// pasėlių.
#include <cstdio>
#include <vector>
using namespace std;
const int MAX_N = 1000;
const int APEJIMU_KIEKIS = 50; // Kuo didesnis, tuo programa lėtesnė, bet tikslesnė.
const int PASELIS = 20180324; // Pseudoatsitiktinių skaičių generavimui.
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 = rand() % 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[rand() % 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()
{
srand(PASELIS);
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
sauga.cpp: In function 'void Spausdinti()':
sauga.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 0; i < evakuojami_prasizengiant.size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int i = 0; i < evakuojami_pradzioje.size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'void PerziuretiLikusiusPastatus()':
sauga.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i < like_pastatai.size(); )
| ~~^~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'void EvakuotiPastata(int, std::vector<int>&)':
sauga.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int j = 0; j < pastatai[i].ankstesni.size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (int j = 0; j < pastatai[i].velesni.size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'int PasirinktiIsejima(int)':
sauga.cpp:127:17: error: 'rand' was not declared in this scope
127 | int r = rand() % pastatai[i].velesni.size();
| ^~~~
sauga.cpp: In function 'int RastiSvarbiausiaPastata()':
sauga.cpp:143:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for (int i = 0; i < like_pastatai.size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:146:40: error: 'rand' was not declared in this scope
146 | int dabar_lankomas = like_pastatai[rand() % like_pastatai.size()];
| ^~~~
sauga.cpp:150:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for (int t = 0; t < like_pastatai.size() * APEJIMU_KIEKIS; ++t) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'void PaliktiMaziausiaiTrukdanti()':
sauga.cpp:167:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for (int i = 0; i < like_pastatai.size(); ++i) {
| ~~^~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:176:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | for (int j = 0; j < pastatai[maziausiai_ankstesniu].ankstesni.size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:181:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | for (int j = 0; j < pastatai[maziausiai_velesniu].velesni.size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'int main()':
sauga.cpp:189:5: error: 'srand' was not declared in this scope
189 | srand(PASELIS);
| ^~~~~
sauga.cpp: In function 'void Nuskaityti()':
sauga.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%*d%d%d", &N, &riba); // Testo numeris šiam sprendimui nesvarbus.
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d", &pastatai[i].n_ankstesni);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d", &k);
| ~~~~~^~~~~~~~~~
