TÓPICO

PROBLEM 1778 - URI Fórum 1.0

beecrowd perguntou 9 years ago

URI Online Judge Fórum 1.0

MOD

Este tópico foi resolvido e não pode receber novas respostas.

  • gduarte respondido 8 years ago

    Não encontrei o erro, então apaguei meu código e fiz outro e passou :)

    MOD

  • Joao40 respondido 8 years ago

    Seu código ta muito parecido com o meu, não tenho ideia do porquê dos 40% :/

  • gduarte respondido 8 years ago

    Exatamente isso que eu fiz, só que eu já marco o vértice do castelo como visitado, assim ele nunca será inserido. Segue meu código:

    ACC
    MOD

  • Joao40 respondido 8 years ago

    Quando faz a BFS, você não pode colocar o vértice F na fila quando achar ele, aquele caminho que você tava seguindo deve ser cortado (os danos antes de chegar em F são mantidos) já que não da pra continuar por ele porque dessa forma o castelo estaria propagando o ataque, o que é impossível segundo o exercício. Resumindo: o vértice atual é diferente de F? Sim: posso continuar nesse caminho (insere na fila). Não: continuo calculando os danos em outros caminhos (não insere).

  • gduarte respondido 8 years ago

    Mas isso não significa que quando for fazer a busca em largura para aplicar os danos eu não devo nunca empilhar o vértice F ? Foi assim que pensei e parece que faz sentido.

    MOD

  • Joao40 respondido 8 years ago

    Depois de muito tempo consegui passar esse exercício. Você ta considerando essa parte? "O castelo possui um escudo mágico protetor que faz com que nenhuma torre consiga atacar o vértice F onde ele se encontra, tampouco propagar o ataque, ou seja, o vértice F é uma barreira e nada passa por ele, a não ser os monstros, possivelmente.", um dos meus erros era nessa parte.

  • gduarte respondido 8 years ago

    Alguem pode me passar mais alguns casos de teste ? Estou recebendo WA 40% e não faz sentido.

    MOD

  • Joao40 respondido 8 years ago

    Fiz uma BFS pra cada torre pra calcular os danos, depois fiz só um Dijkstra partindo do castelo pra ver o menor caminho até os demais vértices mas tomo TLE. Alguém sabe por que?? Obrigado.

    ACC

  • rtashiro0 respondido 8 years ago

    Estou recebendo TLE e não sei onde está o gargalo, alguma dica?

    #include <bits/stdc++.h>

#define INF 100000
#define MAXV 1005

using namespace std;

void setTowerDmg( int pos, int dmg, int reach, list<int> *graph, int *dmgTable )
{
    queue<pair<int,int>> fil;
    int visited[MAXV] = {0};
    fil.push( {pos,0} );
    while( !fil.empty() ) {
        pair<int,int> act = fil.front();
        visited[get<0>(act)] = 1;
        fil.pop();
        for( auto& a : graph[get<0>(act)] ) {
            if( get<1>(act) < reach && !visited[a] ) {
                fil.push( {a,get<1>(act)+1} );
                dmgTable[a] += dmg;
            }
        }
    }
}

int *dijkstra( int pos, list<int> *graph, int *dmgTable )
{
    int *w = ( int* ) malloc( sizeof( int ) * MAXV );
    memset( w, INF, sizeof( int ) * MAXV );
    int visited[MAXV] = {0};
    queue<int> fil;
    fil.push( pos ), w[pos] = 0, visited[pos] = 1;
    while( !fil.empty() ) {
        int act = fil.front();
        fil.pop();
        for( auto& a : graph[act] ) {
            if( !visited[a] ) {
                fil.push( a ), visited[a] = 1;
                w[a] = max( w[act] + dmgTable[a], w[a] );
            }
        }
    }
    return w;
}

int main()
{
    ios::sync_with_stdio( false );

    int T, caso = 1;

    cin >> T;

    while( T-- )
    {
        int N, M, F; // Number of vertex, edge and castle position

        cin >> N >> M >> F;

        list<int> graph[N+1];
        int dmgTable[N+1];
        memset( dmgTable, 0, sizeof( dmgTable ) );

        while( M-- )
        {
            int u, v;
            cin >> u >> v;
            graph[u].push_back( v );
            graph[v].push_back( u );
        }

        int P; // Number of Tower

        cin >> P;

        while( P-- )
        {
            int V, A, C; // Tower position, attack and reach
            cin >> V >> A >> C;
            setTowerDmg( V, A, C, graph, dmgTable );
        }

        dmgTable[F] = 0; // Castle has no damage
        int *vert = dijkstra( F, graph, dmgTable );

        int Q, succeful = 0; //  Number of monster and number of monster that
                             //  reach the castle
        cin >> Q;

        while( Q-- )
        {
            int K, H; // Spawn vertex and life points
            cin >> K >> H;
            if( K == F || vert[K] < H ) succeful++;
        }

        cout << "Caso #" << caso++ << ": " << succeful << "\n";
    }

    return 0;
}

  • mmarques1 respondido 8 years ago

    Segui a mesma ideia do Alexandre porém estou recebendo 30% W.A ou TLE alguma ideia?

    #include <iostream>
#include <stdio.h>
#include <list> //adjacency list
#include <utility> //pair make_pair
#include <string.h> //memset
#include <queue> //priority queue
#include <vector>

#define MAXV 1100
#define DIST_MAX 1000000000000

typedef long long int lli;

using namespace std;

lli dist[MAXV]; //distance
lli parent[MAXV]; //parent node
lli danovert[MAXV];
lli visited[MAXV];
list<lli>Grafo[MAXV];
list<lli>::iterator lit;
queue<lli>wq; //wait queue
lli n_vert, n_edge; //number of vertices and edges

struct Node
{
public:
    lli a;
    Node(lli x){a = x;} //constructor
    bool operator<(const struct Node p2) const{
        return dist[a] > dist[p2.a];
    }
};

void Dijkstra(lli root);

int main()
{
    lli T, n_torres, posC;
    lli i, j, k, v1, v2;
    lli vt, cl, vm;
    lli at, vi, n_monstros;
    lli breadth;

    scanf("%lld", &T);
    for(i=0; i<T; i++)
    {
        scanf("%lld %lld %lld", &n_vert, &n_edge, &posC);

        for(j=1; j<=n_vert; j++)
            Grafo[j].clear();
        memset(danovert, 0, MAXV);

        for(j=0; j<n_edge; j++){
            scanf("%lld %lld", &v1, &v2);
            Grafo[v1].push_back(v2);
            Grafo[v2].push_back(v1);
        }

        scanf("%lld", &n_torres);
        for(j=0; j<n_torres; j++){
            scanf("%lld %lld %lld", &vt, &at, &cl);
            /*clear preparate to bfs */
            while(!wq.empty()) wq.pop();
            breadth = 1;
            memset(visited, 0, MAXV);
            /*bfs*/
            wq.push(vt);

            if(cl>=n_vert){
                for(k=1; k<=n_vert; k++)
                    danovert[k]+=at;
                continue;
            }

            while(!wq.empty())
            {
                if(!visited[wq.front()]){
                    visited[wq.front()] = breadth++;
                    if(visited[wq.front()]<=cl+1){ //se estiver no alcance
                        danovert[wq.front()]+=at; // ataque
                        //printf("Vertice %lld atacado por %lld com %lld\n", wq.front(), vt, at);
                    }
                }
                for(lit=Grafo[wq.front()].begin(); lit!=Grafo[wq.front()].end(); lit++){
                    if(!visited[*lit]){
                        visited[*lit] = visited[wq.front()]+1;
                        if(visited[*lit]<=cl+1){ //se estiver no alcance
                            danovert[*lit]+=at; //ataque
                            //printf("Vertice %lld atacado por %lld com %lld\n", *lit, vt, at);
                        }
                    wq.push(*lit);
                    }
                }
                if(breadth>=cl+1) break;
                wq.pop();
            }
        }
        danovert[posC] = 0; //o castelo é protegido

        //for(j=1; j<=n_vert; j++)
        //  printf("Vertice %lld recebe %lld por u.t\n", j, danovert[j]);

        Dijkstra(posC);
        lli monstros_vivos = 0;
        scanf("%lld", &n_monstros);
        for(j=0; j<n_monstros; j++){
            scanf("%lld %lld", &vm, &vi);
            if(dist[vm] < vi)
                monstros_vivos++;
        }

        printf("Caso #%lld: %lld\n", i+1, monstros_vivos);
    }

    return 0;
}

void Dijkstra(lli root)
{
    for(lli i=1; i<=n_vert; i++)
    {
        dist[i] = DIST_MAX;
        parent[i] = -1;
    }
    dist[root] = 0;

    priority_queue<Node> mypq;
    while(!mypq.empty()) 
        mypq.pop();
    mypq.push(root);

    lli v_dest, weight;
    lli act; //actual vertex

    while(!mypq.empty())
    {
        act = mypq.top().a;
        mypq.pop();
        //cout << "\nActual Node: " << act << endl;
        for(lit=Grafo[act].begin(); lit!=Grafo[act].end(); lit++) //similar to bfs
        {
            //cout << it->first << " ";
            v_dest = *lit;
            weight = danovert[*lit];
            if(dist[v_dest] > dist[act]+weight) //replace
            {
                //cout << "replaced ";
                parent[v_dest] = act;
                dist[v_dest] = dist[act]+weight;
                mypq.push(Node(v_dest));
            }
        }
    }
}

  • avasconcellos respondido 8 years ago

    Opa, obrigado pela resposta. Eu faço um dijkstra só para calcular o dano de todos os vértices. Até usei fila de prioridade na ultima tentativa.

  • gdlima respondido 8 years ago

    A ideia é essa mesmo, alexandre. Só da uma pensada e vê se é necessário um dijkstra para cada vértice, ou se tem uma maneira melhor de resolver essa parte.

    Abraço!

  • avasconcellos respondido 8 years ago

    Só recebo TLE neste problema =/

    Minha ideia foi fazer uma BFS para cada torre para calcular o dano em cada vértice. Depois um dijkstra para calcular o dano do caminho de cada vertice até o castelo. Assim podia responder se cada monstro sobreviveria instantaneamente. Acho que o gargalo ficou nas BFS. Tentei unir torres no mesmo vértice e com mesmo alcance na mesma BFS ou usar um método em que o vetor visitados não precisava ser zerado a cada BFS. Mas só da TLE =/ Essa é uma abordagem ruim? Alguem pode me dar uma dica?

  • igormalheiros respondido 8 years ago

    Alguém tem casos extremos? Estou tomando WA 10% e não sei mais o que fazer...