답안 #455145

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
455145 2021-08-05T13:56:15 Z Kipras Fire drill (LMIO18_sauga) C++14
98.7437 / 100
431 ms 7620 KB
// 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 <bits/stdc++.h>

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:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 0; i < evakuojami_prasizengiant.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < evakuojami_pradzioje.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'void PerziuretiLikusiusPastatus()':
sauga.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 0; i < like_pastatai.size(); )
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'void EvakuotiPastata(int, std::vector<int>&)':
sauga.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int j = 0; j < pastatai[i].ankstesni.size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for (int j = 0; j < pastatai[i].velesni.size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'int RastiSvarbiausiaPastata()':
sauga.cpp:142:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for (int i = 0; i < like_pastatai.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:149:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for (int t = 0; t < like_pastatai.size() * APEJIMU_KIEKIS; ++t) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'void PaliktiMaziausiaiTrukdanti()':
sauga.cpp:166:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     for (int i = 0; i < like_pastatai.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:175:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |         for (int j = 0; j < pastatai[maziausiai_ankstesniu].ankstesni.size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:180:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |         for (int j = 0; j < pastatai[maziausiai_velesniu].velesni.size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp: In function 'void Nuskaityti()':
sauga.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%*d%d%d", &N, &riba); // Testo numeris šiam sprendimui nesvarbus.
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d", &pastatai[i].n_ankstesni);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:58:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |             scanf("%d", &k);
      |             ~~~~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 7512 KB Output is correct
2 Partially correct 43 ms 424 KB Output is partially correct
3 Correct 120 ms 372 KB Output is correct
4 Correct 295 ms 460 KB Output is correct
5 Partially correct 298 ms 556 KB Output is partially correct
6 Partially correct 431 ms 484 KB Output is partially correct
7 Correct 56 ms 1612 KB Output is correct
8 Correct 73 ms 7620 KB Output is correct
9 Partially correct 23 ms 1076 KB Output is partially correct
10 Correct 156 ms 420 KB Output is correct