Zadanie Morskie Opowieści Grafy

Question

Mam problem z zadaniem morskie opowieści. Co zauważyłem: po 1 na pytania musimy odpowiedzieć w czasie stałym, tylko trzeba jakoś naliczyć drogi. Po 2, jeśli istnieje najkrótsza droga z x do y, o dlugosci x, to wszystkie >= x o tej samej parzystości się da, bo można chodzić po jednej krawędzi w kółko, w sensie; te o x,x+2,x+4,x+6... też się da. Tylko nie wiem jak znaleźć najkrótszą drogę o przeciwnej parzystości niż najktrótsza droga. Kompletnie nic mi nie przychodzi do głowy.

edit: znalazłem treść na szkopule:
https://szkopul.edu.pl/problemset/problem/CfSEK4ACOcAPaAfX29Fp7Tud/site/?key=statement

Z góry dziękuję za pomoc i poświęcony czas!

Answer 1

Trick pod nazwą "graf warstwowy". Zduplikujmy cały graf. Mamy 2*n wierzchołków i 2*m krawędzi. n wierzchołków i m krawędzi należy do warstwy 1, pozostałe do warstwy 2. Miedzy wierzchołkami w tej samej warstwie nie ma krawędzi. Jest krawędź v1 <-> v2 wtw. gdy v1, v2 są w różnych warstwach i istniała krawędź między odpowiadającymi wierzchołkami w grafie podanym na wejściu. Jak korzystając z tego rozwiązać zadanie?

Comments

btw ten sam trick można zastosować do rozwiązania zadania Magazynier

---

Zrobiłem coś takiego tym twoim pomysłem, w 4 testach dostaje wrong answer. Wiesz gdzie jest błąd? btw, wiem, że muszę lepiej ztablicować (po każdym zapytaniu, żeby pamięć przeszła), ale narazie chce WA usunąć:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Element_kolejki
{
    int v;
    bool czy_parzyste;
};

int n = 0, m = 0, k = 0, a_i = 0, b_i = 0, c_i;
Element_kolejki spr = {-1,true};
vector<vector<int>> krawedzie;
vector<vector<int>> dystans_parzyste;
vector<vector<int>> dystans_nie_parzyste;
queue<Element_kolejki> Q;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;
    krawedzie.assign(n+1,{});
    for (int i = 0; i <= n; ++i)
    {
        dystans_parzyste.push_back({});
        dystans_nie_parzyste.push_back({});
        for (int j = 0; j <= n; ++j)
        {
            dystans_parzyste[i].push_back(-1);
            dystans_nie_parzyste[i].push_back(-1);
        }
    }
    for (int i = 0; i < m; ++i)
    {
        cin >> a_i >> b_i;
        krawedzie[a_i].push_back(b_i);
        krawedzie[b_i].push_back(a_i);
    }

    for (int i = 1; i <= n; ++i)
    {
        while(!Q.empty())
            Q.pop();
        Q.push({i,true});
        dystans_parzyste[i][i] = 0;
        while (!Q.empty())
        {
            spr = Q.front();
            for (int j = 0; j < krawedzie[spr.v].size(); ++j)
            {
                if (spr.czy_parzyste == true)
                {
                    if (dystans_nie_parzyste[i][krawedzie[spr.v][j]] == -1)
                    {
                        dystans_nie_parzyste[i][krawedzie[spr.v][j]] = dystans_parzyste[i][spr.v] + 1;
                        Q.push({krawedzie[spr.v][j],false});
                    }
                }
                else
                {
                    if (dystans_parzyste[i][krawedzie[spr.v][j]] == -1)
                    {
                        dystans_parzyste[i][krawedzie[spr.v][j]] = dystans_nie_parzyste[i][spr.v] + 1;
                        Q.push({krawedzie[spr.v][j],true});
                    }
                }
            }
            Q.pop();
        }
    }

    for (int i = 0; i < k; ++i)
    {
        cin >> a_i >> b_i >> c_i;
        if (c_i % 2 == 0)
        {
            if (c_i >= dystans_parzyste[a_i][b_i] && dystans_parzyste[a_i][b_i] != -1)
                cout << "TAK" << '\n';
            else
                cout << "NIE" << '\n';
        }
        else
        {
            if (c_i >= dystans_nie_parzyste[a_i][b_i] && dystans_nie_parzyste[a_i][b_i] != -1)
                cout << "TAK" << '\n';
            else
                cout << "NIE" << '\n';
        }
    }
    return 0;
}

 

---

Dobra błąd był w lini 50: dystans_parzyste[i][i] = 0; co jest nieprawdą, więc trzeba usunąć tą linię. Przeszło na 80. Musze lepiej ztablicować(zpamiętać zapytania) i pewnie wejdzie (pamięć się wywaliła)

---

Przeszło na 100. Dzięki za pomoc! Bardzo fajny pomysł. Ciężko go byłoby samemu wymyśleć za pierwszym razem, a jak już ktoś raz powie, to może się wpadnie kolejnym razem na tosamo / podobne.

Krótki opis, jak ktoś by się kiedyś męczył:

Zapytania trzeba ztablicować (nawet nie wystarczy odpalić dla każdej z 1,n BFS-a i trzymac w 2 wymiarowej tablicy (pamięc się przekracza), więc ja zapisałem, posortowałem sobie zapytania po początkach i dla każdego którego jeszcze nie sprawdziłem odpaliłem tego BFS-a. I miałem jeszcze jakiś vector wyników, ale to wiadomo.

Kod:

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Element_kolejki
{
    int v;
    bool czy_parzyste;
};

struct Zapytanie
{
    int poczatek;
    int koniec;
    int d;
    int idx;
    bool operator < (const Zapytanie &zapytanie) const
    {
        return poczatek < zapytanie.poczatek;
    }
};

int n = 0, m = 0, k = 0, a_i = 0, b_i = 0, c_i, wartosc_sprawdzona = 0;
Element_kolejki spr = {-1,true};
vector<vector<int>> krawedzie;
vector<int> dystans_parzyste; // Dystans z wierzcholka wartosc_sprawdzona do kazdego(o idxie 1,2,3,4...)
vector<int> dystans_nie_parzyste; // Dystans z wierzcholka wartosc_sprawdzona do kazdego(o idxie 1,2,3,4...)
vector<Zapytanie> zapytania;
vector<bool> wyniki_zapytan;
queue<Element_kolejki> Q;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;
    wyniki_zapytan.assign(k,false);
    dystans_parzyste.assign(n+1,-1);
    dystans_nie_parzyste.assign(n+1,-1);
    krawedzie.assign(n+1,{});
    for (int i = 0; i < m; ++i)
    {
        cin >> a_i >> b_i;
        krawedzie[a_i].push_back(b_i);
        krawedzie[b_i].push_back(a_i);
    }
    for (int i = 0; i < k; ++i)
    {
        cin >> a_i >> b_i >> c_i;
        zapytania.push_back({a_i,b_i,c_i, i});
    }
    sort(zapytania.begin(),zapytania.end());

    for (int i = 0; i < k; ++i)
    {
        if (zapytania[i].poczatek != wartosc_sprawdzona)
        {
            dystans_parzyste.assign(n+1,-1);
            dystans_nie_parzyste.assign(n+1,-1);
            wartosc_sprawdzona = zapytania[i].poczatek;
            while(!Q.empty())
                Q.pop();
            Q.push({zapytania[i].poczatek,true});
            while(!Q.empty())
            {
                spr = Q.front();
                for (int j = 0; j < krawedzie[spr.v].size(); ++j)
                {
                    if (spr.czy_parzyste == true)
                    {
                        if (dystans_nie_parzyste[krawedzie[spr.v][j]] == -1)
                        {
                            dystans_nie_parzyste[krawedzie[spr.v][j]] = dystans_parzyste[spr.v] + 1;
                            Q.push({krawedzie[spr.v][j],false});
                        }
                    }
                    else
                    {
                        if (dystans_parzyste[krawedzie[spr.v][j]] == -1)
                        {
                            dystans_parzyste[krawedzie[spr.v][j]] = dystans_nie_parzyste[spr.v] + 1;
                            Q.push({krawedzie[spr.v][j],true});
                        }
                    }
                }
                Q.pop();
            }
        }
        if (zapytania[i].d % 2 == 0)
        {
            if (dystans_parzyste[zapytania[i].koniec] != -1 && zapytania[i].d >= dystans_parzyste[zapytania[i].koniec])
                wyniki_zapytan[zapytania[i].idx] = true;
        }
        else
        {
            if (dystans_nie_parzyste[zapytania[i].koniec] != -1 && zapytania[i].d >= dystans_nie_parzyste[zapytania[i].koniec])
                wyniki_zapytan[zapytania[i].idx] = true;
        }
    }

    for (int i = 0; i < k; ++i)
    {
        if (wyniki_zapytan[i] == true)
            cout << "TAK" << '\n';
        else
            cout << "NIE" << '\n';
    }

    return 0;
}

Na początku jak robiłem to zadanie, to znalazłem w necie omówienie tu: https://www.youtube.com/watch?v=_ZEwenrQeZI&list=PLf5PhqE3dbQULL-XaVyzS5EbKzcU9V-Bw&index=5&t=2316s

Ogólnie robią dobre omówienia, ale akurat tego nie zrozumiałem.

A no i natknąłem się na ciekawe zadania na BFS-a na dziwnym grafie, agenci z finału 7OI-a i wiedzmak z OI polecam, je zrobić po zrobieniu tego.

Jeszcze raz dzięki!

---

@Whistleroosh, 

Znasz jeszcze jakieś ciekawe zadania grafowe, oprócz wspomnianego magazyniera? 

---

Zadanie Długie Podróże XXVI OI. Genialne zadanie na nietypowy pomysł