TÓPICO

PROBLEM 1778 - URI Fórum 1.0

URI Online Judge perguntou 6 years ago

URI Online Judge Fórum 1.0

MOD

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

  • Gabriel Duarte respondido 5 years ago

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

    MOD
  • João respondido 5 years ago

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

  • Gabriel Duarte respondido 5 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
  • João respondido 5 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).

  • Gabriel Duarte respondido 5 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
  • João respondido 5 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.

  • Gabriel Duarte respondido 5 years ago

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

    MOD
  • João respondido 5 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
  • 🎈Renan Tashiro🎈 respondido 5 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;
    }
  • Marcello Marques respondido 5 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));
                }
            }
        }
    }
  • Alexandre Vasconcellos respondido 5 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.

  • Guilherme de Lima respondido 5 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!

  • Alexandre Vasconcellos respondido 5 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?

  • Igor Malheiros respondido 5 years ago

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