• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie żywopłot, finał XXIII OI

VPS Starter Arubacloud
0 głosów
213 wizyt
pytanie zadane 13 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 13 kwietnia 2023 przez pasjonat_algorytmiki
Mam problem z zadaniem żywopłot z finału XXIII OI: https://szkopul.edu.pl/problemset/problem/dABzva_j1-BvzKMsyxkuRoue/site/?key=statement

Nie wiem jak je zrobić, oprócz jakiegoś wykładniczego bruta na 25pkt.

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

1 odpowiedź

+1 głos
odpowiedź 13 kwietnia 2023 przez Whistleroosh Maniak (56,900 p.)
wybrane 14 kwietnia 2023 przez pasjonat_algorytmiki
 
Najlepsza
Taka prosta obserwacja. Załóżmy, że pola to wierzchołki w grafie. Jeśli jest przejście między 2 polami to jest krawędź między odpowiadającymi wierzchołkami w grafie. Dla poprawnego labiryntu jakiej postaci jest ten graf?
komentarz 13 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
chwila chwila, da się chyba to O(N*M) zrobić! Bierzemy algorytm Prima, i modyfikujemy go tak jak Dijkstrę 0-1 robiąc na deque zamist kolejki priorytetowej / seta.
komentarz 13 kwietnia 2023 przez Whistleroosh Maniak (56,900 p.)
No tak, i to jest wzorcówka
komentarz 14 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 14 kwietnia 2023 przez pasjonat_algorytmiki

Napisałem taki kod:

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

enum Kierunek
{
    GORA, DOL, LEWO, PRAWO, BRAK
};

struct Pole
{
    int y;
    int x;
    Kierunek kier;
    int val;
};

int n = 0, m = 0, wyn_cis = 0, wyn_inne = 0;
char wczytany_znak;
vector<vector<int>> dp;
vector<vector<int>> krawedzie_gora;
vector<vector<int>> krawedzie_dol;
vector<vector<int>> krawedzie_lewo;
vector<vector<int>> krawedzie_prawo;
deque<Pole> Q;
vector<vector<bool>> czy_w_MST_pionowe;
vector<vector<bool>> czy_w_MST_poziome;

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

    cin >> n >> m;

    dp.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        dp[i].assign(m+2,1e9);

    krawedzie_gora.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_gora[i].assign(m+2,0);

    krawedzie_dol.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_dol[i].assign(m+2,0);

    krawedzie_lewo.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_lewo[i].assign(m+2,0);

    krawedzie_prawo.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_prawo[i].assign(m+2,0);

    czy_w_MST_poziome.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        czy_w_MST_poziome[i].assign(m+1,false);

    czy_w_MST_pionowe.assign(n+1,{});
    for (int i = 1; i <= n; ++i)
        czy_w_MST_pionowe[i].assign(m+2,false);

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2; j <= m; ++j)
        {
            cin >> wczytany_znak;
            if (wczytany_znak == 'T')
            {
                krawedzie_dol[i][j] = 1;
                krawedzie_gora[i+1][j] = 1;
            }
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin >> wczytany_znak;
            if (wczytany_znak == 'T')
            {
                krawedzie_prawo[i][j] = 1;
                krawedzie_lewo[i][j+1] = 1;
            }
        }
    }

    for (int j = 1; j <= m+1; ++j)
    {
        dp[1][j] = 0;
        Q.push_back({1,j,BRAK,0});
    }
    for (int j = 1; j <= m+1; ++j)
    {
        dp[n+1][j] = 0;
        Q.push_back({n+1,j,BRAK,0});
    }
    for (int i = 2; i <= n; ++i)
    {
        dp[i][1] = 0;
        Q.push_back({i,1,BRAK,0});
    }
    for (int i = 2; i <= n; ++i)
    {
         dp[i][m+1] = 0;
         Q.push_back({i,m+1,BRAK,0});
    }

    while(!Q.empty())
    {
        Pole spr = Q.front();
        Q.pop_front();
        if (spr.val > dp[spr.y][spr.x])
            continue;
        if (spr.kier != BRAK)
        {
            if (spr.kier == LEWO)
                czy_w_MST_poziome[spr.y][spr.x-1] = true;
            else if (spr.kier == PRAWO)
                czy_w_MST_poziome[spr.y][spr.x] = true;
            if (spr.kier == GORA)
                czy_w_MST_pionowe[spr.y-1][spr.x] = true;
            else if (spr.kier == DOL)
                czy_w_MST_pionowe[spr.y][spr.x] = true;
        }
        if (spr.y - 1 >= 1)
        {
            if (dp[spr.y-1][spr.x] == false)
            {
                if (krawedzie_gora[spr.y][spr.x] == 0)
                {
                    if (0 < dp[spr.y-1][spr.x])
                    {
                        dp[spr.y-1][spr.x] = 0;
                        Q.push_front({spr.y-1, spr.x,DOL, 0});
                    }
                }
                else
                {
                    if (1 < dp[spr.y-1][spr.x])
                    {
                        dp[spr.y-1][spr.x] = 1;
                        Q.push_back({spr.y-1, spr.x, DOL,1});
                    }
                }
            }
        }
        if (spr.y + 1 <= n+1)
        {
            if (krawedzie_dol[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y+1][spr.x])
                {
                    dp[spr.y+1][spr.x] = 0;
                    Q.push_front({spr.y+1, spr.x, GORA,0});
                }
            }
            else
            {
                if (1 < dp[spr.y+1][spr.x])
                {
                    dp[spr.y+1][spr.x] = 1;
                    Q.push_back({spr.y+1, spr.x, GORA,1});
                }
            }
        }
        if (spr.x - 1 >= 1)
        {
            if (krawedzie_lewo[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y][spr.x-1])
                {
                    dp[spr.y][spr.x-1] = 0;
                    Q.push_front({spr.y, spr.x-1, PRAWO,0});
                }
            }
            else
            {
                if (1 < dp[spr.y][spr.x-1])
                {
                    dp[spr.y][spr.x-1] = 1;
                    Q.push_back({spr.y, spr.x-1, PRAWO,1});
                }
            }
        }
        if (spr.x + 1 <= m+1)
        {
            if (krawedzie_prawo[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y][spr.x+1])
                {
                    dp[spr.y][spr.x+1] = 0;
                    Q.push_front({spr.y, spr.x+1, LEWO,0});
                }
            }
            else
            {
                if (1 < dp[spr.y][spr.x+1])
                {
                    dp[spr.y][spr.x+1] = 1;
                    Q.push_back({spr.y, spr.x+1, LEWO,1});
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2; j <= m; ++j)
        {
            if (czy_w_MST_pionowe[i][j] == true)
            {
                if (krawedzie_dol[i][j] == 0)
                {
                    wyn_cis++;
                }
                else
                {
                    wyn_inne++;
                }
            }
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (czy_w_MST_poziome[i][j] == true)
            {
                if (krawedzie_prawo[i][j] == 0)
                {
                    wyn_cis++;
                }
                else
                {
                    wyn_inne++;
                }
            }
        }
    }
    cout << wyn_cis+wyn_inne << ' ' << wyn_cis << '\n';

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2; j <= m; ++j)
        {
            if (czy_w_MST_pionowe[i][j] == true)
                cout << 'Z';
            else
                cout << '.';
        }
        cout << '\n';
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (czy_w_MST_poziome[i][j] == true)
                cout << 'Z';
            else
                cout << '.';
        }
        cout << '\n';
    }

    return 0;
}

Mam gdzieś błąd, o ile robiłeś to zadanie, to wyślesz kod dający 100pkt, i napiszę sobie sprawdzarkę i sprawdzę co jest źle? Przechodzi wszystkie testy na wstępnym sprawdzaniu, ale wywala się w kilku testach właściwych. Wypisuje zamało z cisem.

1
komentarz 14 kwietnia 2023 przez Whistleroosh Maniak (56,900 p.)
#include <bits/stdc++.h>

typedef unsigned short us;
typedef unsigned long ul;
typedef long l;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const l INF = 1e9 + 9;
const l MOD = 1e9 + 7;
const l PRIME = 200003;
const ll L_INF = 1e18 + 1;
const double EPS = 10e-9;

#define FOR(x, y, z) for (l z = x; z < y; z++)
#define FORE(x, y, z) for (l z = x; z <= y; z++)
#define FORD(x, y, z) for (l z = x; z > y; z--)
#define FORDE(x, y, z) for (l z = x; z >= y; z--)
#define REP(x, y) for (l y = 0; y < x; y++)

#define PF push_front
#define POF pop_front
#define PB push_back
#define POB pop_back
#define MP make_pair
#define FS first
#define SC second

using namespace std;

l n, m, all_cis, cis, all_tuja, tuja;
l group_size[1000005], leader[1000005];
vector<pair<l, l> > graph[2];
set<l> path[1000005];

l FIND(l v)
{
    if(leader[v] != v)
        leader[v] = FIND(leader[v]);

    return leader[v];
}

void UNION(l a, l b)
{
    l l_a = FIND(a);
    l l_b = FIND(b);

    if(group_size[l_a] > group_size[l_b])
    {
        group_size[l_a] += group_size[l_b];
        leader[l_b] = leader[l_a];
    }

    else
    {
        group_size[l_b] += group_size[l_a];
        leader[l_a] = leader[l_b];
    }
}

int main()
{
    cin >> n >> m;

    REP(n*m, i)
    {
        group_size[i+1] = 1;
        leader[i+1] = i+1;
    }

    FORE(1, n, i)
    {
        FORE(1, m-1, j)
        {
            char a;
            cin >> a;

            l pos = (i-1)*m+j;

            if(a == 'C')
            {
                graph[1].PB({pos, pos+1});
                all_cis++;
            }

            else
            {
                graph[0].PB({pos, pos+1});
                all_tuja++;
            }
        }
    }

    FORE(1, n-1, i)
    {
        FORE(1, m, j)
        {
            char a;
            cin >> a;

            l pos = (i-1)*m+j;

            if(a == 'C')
            {
                graph[1].PB({pos, pos+m});
                all_cis++;
            }

            else
            {
                graph[0].PB({pos, pos+m});
                all_tuja++;
            }
        }
    }

    for(auto v: graph[0])
    {
        if(FIND(v.FS) != FIND(v.SC))
        {
            UNION(v.FS, v.SC);
            path[v.FS].insert(v.SC);
            tuja++;
        }
    }

    for(auto v: graph[1])
    {
        if(FIND(v.FS) != FIND(v.SC))
        {
            UNION(v.FS, v.SC);
            path[v.FS].insert(v.SC);
            cis++;
        }
    }

    cout << (all_cis-cis) + (all_tuja-tuja) << " ";
    cout << all_cis-cis << "\n";

    FORE(1, n, i)
    {
        FORE(1, m-1, j)
        {
            l pos = (i-1)*m+j;

            if(path[pos].find(pos+1) != path[pos].end() || path[pos+1].find(pos) != path[pos+1].end())
                cout << ".";

            else
                cout << "Z";
        }

        cout << "\n";
    }

    FORE(1, n-1, i)
    {
        FORE(1, m, j)
        {
            l pos = (i-1)*m+j;

            if(path[pos].find(pos+m) != path[pos].end() || path[pos+m].find(pos) != path[pos+m].end())
                cout << ".";

            else
                cout << "Z";
        }

        cout << "\n";
    }
}

 

1
komentarz 14 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 14 kwietnia 2023 przez pasjonat_algorytmiki

Przeszło, miałem jednego złego if-a.

Kod dający 100pkt, O(N*M), Algorytm Prima na Deque.

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

enum Kierunek
{
    GORA, DOL, LEWO, PRAWO, BRAK
};

struct Pole
{
    int y;
    int x;
    Kierunek kier;
    int val;
};

int n = 0, m = 0, wyn_cis = 0, wyn_inne = 0;
char wczytany_znak;
vector<vector<int>> dp;
vector<vector<int>> krawedzie_gora;
vector<vector<int>> krawedzie_dol;
vector<vector<int>> krawedzie_lewo;
vector<vector<int>> krawedzie_prawo;
deque<Pole> Q;
vector<vector<bool>> czy_w_MST_pionowe;
vector<vector<bool>> czy_w_MST_poziome;
vector<vector<bool>> visited;

int main()
{
    // O(N*M), MST, algorytm Prima na deque(zamiast kolejki priorytetowej / seta, bo wagi na krawedziach to 0 i 1, robimy tak jak Dijkstra 0-1 na deque)
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    dp.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        dp[i].assign(m+2,1e9);

    krawedzie_gora.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_gora[i].assign(m+2,0);

    krawedzie_dol.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_dol[i].assign(m+2,0);

    krawedzie_lewo.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_lewo[i].assign(m+2,0);

    krawedzie_prawo.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_prawo[i].assign(m+2,0);

    czy_w_MST_poziome.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        czy_w_MST_poziome[i].assign(m+1,false);

    czy_w_MST_pionowe.assign(n+1,{});
    for (int i = 1; i <= n; ++i)
        czy_w_MST_pionowe[i].assign(m+2,false);

    visited.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        visited[i].assign(m+2,false);

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2; j <= m; ++j)
        {
            cin >> wczytany_znak;
            if (wczytany_znak == 'T')
            {
                krawedzie_dol[i][j] = 1;
                krawedzie_gora[i+1][j] = 1;
            }
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin >> wczytany_znak;
            if (wczytany_znak == 'T')
            {
                krawedzie_prawo[i][j] = 1;
                krawedzie_lewo[i][j+1] = 1;
            }
        }
    }

    for (int j = 1; j <= m+1; ++j)
    {
        dp[1][j] = 0;
        Q.push_back({1,j,BRAK,0});
    }
    for (int j = 1; j <= m+1; ++j)
    {
        dp[n+1][j] = 0;
        Q.push_back({n+1,j,BRAK,0});
    }
    for (int i = 2; i <= n; ++i)
    {
        dp[i][1] = 0;
        Q.push_back({i,1,BRAK,0});
    }
    for (int i = 2; i <= n; ++i)
    {
         dp[i][m+1] = 0;
         Q.push_back({i,m+1,BRAK,0});
    }

    while(!Q.empty())
    {
        Pole spr = Q.front();
        Q.pop_front();
        if (spr.val > dp[spr.y][spr.x] or visited[spr.y][spr.x] == true)
            continue;
        visited[spr.y][spr.x] = true;
        if (spr.kier != BRAK)
        {
            if (spr.kier == LEWO)
                czy_w_MST_poziome[spr.y][spr.x-1] = true;
            else if (spr.kier == PRAWO)
                czy_w_MST_poziome[spr.y][spr.x] = true;
            if (spr.kier == GORA)
                czy_w_MST_pionowe[spr.y-1][spr.x] = true;
            else if (spr.kier == DOL)
                czy_w_MST_pionowe[spr.y][spr.x] = true;
        }
        if (spr.y - 1 >= 1)
        {
            if (krawedzie_gora[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y-1][spr.x])
                {
                    dp[spr.y-1][spr.x] = 0;
                    Q.push_front({spr.y-1, spr.x,DOL, 0});
                }
            }
            else
            {
                if (1 < dp[spr.y-1][spr.x])
                {
                    dp[spr.y-1][spr.x] = 1;
                    Q.push_back({spr.y-1, spr.x, DOL,1});
                }
            }
        }
        if (spr.y + 1 <= n+1)
        {
            if (krawedzie_dol[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y+1][spr.x])
                {
                    dp[spr.y+1][spr.x] = 0;
                    Q.push_front({spr.y+1, spr.x, GORA,0});
                }
            }
            else
            {
                if (1 < dp[spr.y+1][spr.x])
                {
                    dp[spr.y+1][spr.x] = 1;
                    Q.push_back({spr.y+1, spr.x, GORA,1});
                }
            }
        }
        if (spr.x - 1 >= 1)
        {
            if (krawedzie_lewo[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y][spr.x-1])
                {
                    dp[spr.y][spr.x-1] = 0;
                    Q.push_front({spr.y, spr.x-1, PRAWO,0});
                }
            }
            else
            {
                if (1 < dp[spr.y][spr.x-1])
                {
                    dp[spr.y][spr.x-1] = 1;
                    Q.push_back({spr.y, spr.x-1, PRAWO,1});
                }
            }
        }
        if (spr.x + 1 <= m+1)
        {
            if (krawedzie_prawo[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y][spr.x+1])
                {
                    dp[spr.y][spr.x+1] = 0;
                    Q.push_front({spr.y, spr.x+1, LEWO,0});
                }
            }
            else
            {
                if (1 < dp[spr.y][spr.x+1])
                {
                    dp[spr.y][spr.x+1] = 1;
                    Q.push_back({spr.y, spr.x+1, LEWO,1});
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2; j <= m; ++j)
        {
            if (czy_w_MST_pionowe[i][j] == true)
            {
                if (krawedzie_dol[i][j] == 0)
                    wyn_cis++;
                else
                    wyn_inne++;
            }
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (czy_w_MST_poziome[i][j] == true)
            {
                if (krawedzie_prawo[i][j] == 0)
                    wyn_cis++;
                else
                    wyn_inne++;
            }
        }
    }
    cout << wyn_cis+wyn_inne << ' ' << wyn_cis << '\n';

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2; j <= m; ++j)
        {
            if (czy_w_MST_pionowe[i][j] == true)
                cout << 'Z';
            else
                cout << '.';
        }
        cout << '\n';
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (czy_w_MST_poziome[i][j] == true)
                cout << 'Z';
            else
                cout << '.';
        }
        cout << '\n';
    }

    return 0;
}

Dzięki za pomoc!

Podobne pytania

0 głosów
1 odpowiedź 519 wizyt
pytanie zadane 7 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
0 odpowiedzi 256 wizyt
pytanie zadane 22 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 154 wizyt
pytanie zadane 20 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,454 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...