# TOPIC

PROBLEM 1910 - URI Fórum 1.0

#### URI Online Judge asked 5 years ago

URI Online Judge Fórum 1.0

This topic was solved and cannot recieve new replies.

• #### Allyson Dias de Lima replied 4 years ago

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

``````#include <bits/stdc++.h>

#define FOR(i, a) for(int i = 0; i < a; i++)
#define MAX 100000

using namespace std;

int dist[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(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();

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)
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 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]) {
}
} else {
}
}
}
}

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) {
}
}
}
}
}

int main(){
scanf("%I64d%I64d%I64d", &o, &d, &k);

while (o || d || k) {
for (ll i = 0; i < MAX; i++) {
dist.pb(MAX);
}

for (int i = 0; i < k; i++) {
ll b;
scanf("%I64d", &b);
}

bfs(o);

printf("%I64d\n", ans);

dist.clear();
ans = -1;

scanf("%I64d%I64d%I64d", &o, &d, &k);
}

return 0;
}``````

• #### 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.

Accepted!