TOPIC

PROBLEM 1910 - URI Fórum 1.0

URI Online Judge asked 5 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Allyson Dias de Lima replied 3 years ago

    Alguém pode me ajudar a identificar a causa do Runtime Error no código abaixo?

    Ficarei muito agradecido!

    #include <bits/stdc++.h>
    
    #define FOR(i, a) for(int i = 0; i < a; i++)
    #define MAX 100000
    
    using namespace std;
    
    int dist[100001];
    bool processado[100001], proibido[100001];
    
    int main() {
    
        int O, D, K;
    
        while(scanf("%d %d %d", &O, &D, &K) != EOF) {
    
            if(O == 0 && (D == 0 && K == 0)) break;
    
            memset(proibido, false, sizeof proibido);
            memset(processado, false, sizeof processado);
            memset(dist, -1, sizeof dist);
    
            FOR(i, K) {
                int temp;
                cin >> temp;
                proibido[temp] = true;
            }
    
            //BFS
            deque<int> q;
            q.push_back(O);
            dist[O] = 0;
    
            while(!q.empty()) {
                int v = q.front(); q.pop_front();
                if(!processado[v]) {
                    processado[v] = true;
    
                    int t[5];
    
                    t[0] = v-1;
                    t[1] = v+1;
                    t[2] = v*2;
                    t[3] = v*3;
                    if(v & 1) t[4] = -1;
                    else t[4] = (v >> 1);
    
                    FOR(i, 5) {
                        int u = t[i];
                        if(u <= MAX && u >= 1)
                        if(!processado[u] && !proibido[u]) {
                            q.push_back(u);
                            if(dist[u] == -1) dist[u] = 1 + dist[v];
                        }
                    }
    
                    if(dist[D] != -1) break;
    
                }
    
            }
    
            cout << dist[D] << endl;
    
        }
    
        return 0;
    }
  • Mateus Melo replied 4 years ago

    Troque todos

    %I64d

    por

    %lld

    e levará accepted.

  • Mateus Luna replied 4 years ago

    Estou levando presentation error. Alguém poderia dar uma dica?

    #include <stdio.h>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    //int 10^5, ll 10^18
    #define MAX 100001
    #define ll long long
    #define vi vector <int>
    #define vll vector <ll>
    #define pb push_back
    
    vll adj[MAX];
    vll dist;
    ll o, d, k, ans = -1;
    
    bool valid (ll x) {
        return (x > 0 && x < MAX);
    }
    
    void create_children (ll x) {
        ll children[] = {x/2, x*2, x*3, x+1, x-1};
        bool valids[] = 
        {x%2==0 && x, valid(x*2), valid(x*3), valid(x+1), valid(x-1)};
    
        for (int i = 0; i < 5; i++) {       
            if (valids[i]) {
                if (adj[children[i]].size()) {
                    if (adj[children[i]][0]) {
                        adj[x].pb(children[i]);
                    }
                } else {
                    adj[x].pb(children[i]);
                }
            }
        }
    }
    
    void bfs(ll vertice) {
        queue<ll> q; 
    
        q.push(vertice);
        dist[vertice] = 0;
    
        while (!q.empty()) {
            vertice = q.front();
            q.pop();
    
            if (vertice == d) {
                ans = dist[vertice];
                break;
            } else {
                create_children(vertice);
    
                for (int i = 0; i < (int) adj[vertice].size(); i++) {
                    //printf("father: %I64d child: %I64d\n", vertice, adj[vertice][i]);
    
                    if (dist[adj[vertice][i]] > dist[vertice] + 1) {
                        dist[adj[vertice][i]] = dist[vertice] + 1;
                        q.push(adj[vertice][i]);
                    }
                }
            }
        }
    }
    
    int main(){
        scanf("%I64d%I64d%I64d", &o, &d, &k);
    
        while (o || d || k) {
            for (ll i = 0; i < MAX; i++) {
                dist.pb(MAX);
                adj[i].clear();
            }
    
            for (int i = 0; i < k; i++) {
                ll b;
                scanf("%I64d", &b);
                adj[b].pb(0);
            }
    
            bfs(o);
    
            printf("%I64d\n", ans);
    
            dist.clear();
            ans = -1;
    
            scanf("%I64d%I64d%I64d", &o, &d, &k);
        }
    
        return 0;
    }
  • Samuel Eduardo replied 5 years ago

    Passou. Muito obrigado cara,de verdade :)

  • Mateus Melo replied 5 years ago

    Você está usando o mapa de int para bool. Você pode substituir isto por um vetor. Seu programa ficaria muito mais rápido.

  • Samuel Eduardo replied 5 years ago

    Obrigado cara,mas agora estou recebendo TLE. Alguma sugestão de como deixa-lo mais eficiente ?

  • Mateus Melo replied 5 years ago

    Seu programa encerra nos seguintes casos:

    1 2 0
    2 3 0
    3 4 0

    Perceba que o valor de O e D é sempre maior que zero, mas o valor de K, pode ser igual a zero.

  • Samuel Eduardo replied 5 years ago

    Ainda sou bem noob com grafos,então talvez tenha algum erro bobo kk de qualquer forma,estou aqui pra aprender haha

    Tá ai:

    Accepted !
  • Mateus Melo replied 5 years ago

    Poste seu código. Fica mais fácil de apontar casos.

  • Samuel Eduardo replied 5 years ago

    Alguém tem mais casos de teste ? Obrigado.

  • Mateus Melo replied 5 years ago

    Accepted!