TOPIC

PROBLEM 1955 - URI Fórum 1.0

URI Online Judge asked 4 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Jose Anilto dos Anjos replied 3 years ago

    Tem mais casos de teste?

  • Diego 2.0 replied 3 years ago

    Gente, tentei resolver esse problema percorrendo o grafo implícito, alguém poderia me ajudar? Estou tomando W.A. 30%. VLW :D

    #include <bits/stdc++.h>
    
    using namespace std;
    
    #define ii pair <int, int>
    #define inf 0x3F3F3F
    
    int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1}, grid[10001][10001];
    int cor[10001][10001];
    
    bool ingrid (int x, int y, int n)
    {
        if (x < 0 || x >= n || y < 0 || y >= n)
            return false;
    
        return grid[x][y] == 1;
    }
    
    bool isBipartite (int x, int y, int n)
    {
        bool bipartite = true;
    
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                cor[i][j] = inf;
    
        queue <ii> q;
    
        cor[x][y] = 0;
        q.push (ii (x, y));
    
        while (!q.empty () & bipartite)
        {
            ii d = q.front();
            q.pop();
    
            for (int i = 0; i < 4; i++)
            {
                int a = d.first + dx[i], b = d.second + dy[i];
    
                if (ingrid(a, b, n) && cor[a][b] == inf)
                {
                    cor[a][b] = 1 - cor[d.first][d.second];
                    q.push (ii (a, b));
                }
                else if (ingrid(a, b, n) && cor[a][b] == cor[d.first][d.second])
                {
                    bipartite = false;
                    break;
                }
            }
        }
    
        return bipartite;
    }
    
    int main ()
    {
        int n;
    
        scanf ("%d", &n);
    
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf ("%d", &grid[i][j]);
    
        if (isBipartite(0, 0, n))
            printf ("Bazinga!\n");
        else
            printf ("Fail!\n");
    
        return 0;
    }
  • leandro.zatesko.alunos replied 4 years ago

    Olá. Sou o autor do problema.

    Você pode pôr as orcas 1, 3 e 4 num tanque e as orcas 2 e 5 no outro.

  • teste876 replied 4 years ago

    Neste primeiro caso, não consigo separar o grafo em dois subconjuntos.. 5 1 1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 1 1

    Porque está "Bazinga!" ?