terminate called after throwing an instance of 'std::bad_alloc’ what(): std::bad_alloc
Cannot figure out why.
My code runs perfectly on my local IDE (CodeBlocks).
I even measured the time using chrono.
Algo:
just bfs and checking if the node I’m currently traversing has a gateway as its adjacent position or not.
Here is my code
#include \<bits/stdc++.h\>
using namespace std;
class Graph
{
int v;
list<int> *adj,gate;
public:
Graph(int v);
void addEdge(int v, int w);
void delEdge(int v, int w);
void BFS(int s,int *node1, int *node2);
void addGateway(int v);
};
Graph::Graph(int v){
adj = new list<int> [v];
}
void Graph::addEdge(int v, int w){
adj[v].push_back(w);
}
void Graph::delEdge(int v,int w){
adj[v].remove(w);
}
void Graph::addGateway(int v){
gate.push_back(v);
}
void Graph::BFS(int s, int *node1, int *node2){
bool *visited = new bool[v];
for(int i=0; i<v; i++)
visited[i]=false;
visited[s]=true;
queue <int> q;
q.push(s);
while(!q.empty()){
int po=q.front();
q.pop();
list <int> :: iterator it;
for(it = adj[po].begin(); it != adj[po].end(); it++){
if(!visited[*it]){
visited[*it]=true;
list<int> :: iterator itg;
for( itg = gate.begin(); itg!= gate.end(); itg++){
if(*itg == *it){
*node1 = po;
*node2 = *it;
return ;
}
}
q.push(*it);
}
}
}
}
int main()
{
int N; // the total number of nodes in the level, including the gateways
int L; // the number of links
int E; // the number of exit gateways
cin >> N >> L >> E; cin.ignore();
Graph g(N);
for (int i = 0; i < L; i++) {
int N1; // N1 and N2 defines a link between these nodes
int N2;
cin >> N1 >> N2; cin.ignore();
g.addEdge(N1,N2);
}
for (int i = 0; i < E; i++) {
int EI; // the index of a gateway node
cin >> EI; cin.ignore();
g.addGateway(EI);
}
// game loop
while (1) {
int SI; // The index of the node on which the Skynet agent is positioned this turn
cin >> SI; cin.ignore();
int node1,node2;
g.BFS(SI,&node1, &node2);
g.delEdge(node1,node2);
cout << node1<< " " << node2<< endl;
}
}
@Dhruv-Garg79 If you correctly observe the animation that is shown when you just see the puzzle story (before clicking “Solve it”) you will get your answer. Hence, you don’t need distance to solve this puzzle.
@with_love_KD I was able to solve it using distance array but I think your solution is better.
I understood after watching animation as you mentioned.
If I only break link directly between virus and gate, It will work.
Hello… i would not consider my code as hard coded at all!
It worked in the iDE perfectly fine but when i submitted, it only passed 1 of the validations.
May I find out why?
n, l, e = [int(i) for i in input().split()]
links = []
for i in range(l):
n1, n2 = [int(j) for j in input().split()]
links.append([n1,n2])
getaway = []
for i in range(e):
getaway.append(int(input()))
while True:
si = int(input())
testcases = []
a = 0
for i in getaway:
if sorted([i,si]) in links:
print(' '.join(sorted([str(i),str(si)])))
links.remove(sorted([i,si]))
a = 1
break
if a == 0:
print(' '.join(sorted([str(i) for i in links[0]])))
links.remove(links[0])
Salut à tous !
Je rencontre un problème (en C++) lors des tests de soumission de ce puzzle.
Pour trouver quel lien couper je déroule un BFS jusqu’à rencontrer une passerelle de sortie, à ce moment je coupe le lien entre cette passerelle et son parent.
Lors des tests de base tout se passe bien, le code coupe toujours le dernier lien vers la passerelle la plus proche. Mais lors de la soumission, mon code ne fonctionne pas comme il devrait. Il lui arrive de couper des liens dont aucun des deux bouts n’est une passerelle, ce qui ne devrait pas être possible.
Je ne vois pas du tout d’où ça peut venir, si quelqu’un a une idée je suis preneur.
Hi, i’m having some problem with my code. I can pass all the test cases, but when i get to the validation cases i get the last 2 wrong. I activated the debug mode and realized that, for some reason, the code was not working when 11 was a gate and 0 was a node. In absolutely all the other cases the code works fine, but i had to hard code only this tuple and now i can pass all the validation tests. Does anyone know why is that?
I’m guessing there is a bug in how you handle the indexes in your code. The validation tests are just a symmetric view of the IDE tests for this puzzle, so the map is the same.
Hi I finished the puzzle in Python all local test cases pass.
When I submit my code the last Validator fails. I can not figure out why. Can somebody please help me?
n, l, e = [int(i) for i in input().split()]
connections_list = list()
gateway_list = list()
gateway_link_dict = dict()
for i in range(l):
# n1: N1 and N2 defines a link between these nodes
n1, n2 = [int(j) for j in input().split()]
connections_list.append((n1,n2))
for i in range(e):
ei = int(input()) # the index of a gateway node
gateway_list.append(ei)
gateway_link_dict[ei] = set()
for item in gateway_list:
for n1, n2 in connections_list:
if n1 == item:
print("link found", file=sys.stderr, flush=True)
gateway_link_dict[item].add(n2)
if n2 == item:
print("link found", file=sys.stderr, flush=True)
gateway_link_dict[item].add(n1)
print(f"dict for {item}: {gateway_link_dict[item]} ", file=sys.stderr, flush=True)
# game loop
while True:
link_to_kill = None
si = int(input()) # The index of the node on which the Skynet agent is positioned this turn
# Write an action using print
# To debug: print("Debug messages...", file=sys.stderr, flush=True)
for item in gateway_link_dict.keys():
print(f"checking SI position {si} in {gateway_link_dict[item]}", file=sys.stderr, flush=True)
if si in gateway_link_dict[item]:
print("SI 1 link away", file=sys.stderr, flush=True)
link_to_kill = f"{item} {si}"
gateway_link_dict[item].remove(si)
if not gateway_link_dict[item]:
del gateway_link_dict[item]
break
if not link_to_kill:
for item in gateway_link_dict.keys():
print(f"pop position from {gateway_link_dict[item]}", file=sys.stderr, flush=True)
try:
link_to_kill = f"{gateway_link_dict[item].pop()} {item}"
break
except ValueError:
print("removing item from dict", file=sys.stderr, flush=True)
del gateway_link_dict[item]
# Example: 0 1 are the indices of the nodes you wish to sever the link between
print(link_to_kill)
Bonjour,
J’ai complété les 4 epreuves dans l’IDE mais je n’ai que 25% au final.
Je n’arrive pas à saisir la différence entr code en dur et code ok… ce qui semble être le problème.
merci!
Hey !
Prefer English if you can.
“Hard-code” is everything that is specific to some tests and not “generic”. A “hard-coded” solution is typically a solution that detect which test is played and print the corresponding (pre-computed) result, instead of be able to directly compute the result from any given input.
The validators (the tests which are played when you submit your code) are similar, but different from the IDE’s tests, to avoid a hard-coded solution working in the IDE to be validated on submit.
I could only pass Simple Test and Triple Star, on other two I always have “Timeout: your program did not provide an input in due time.”. C language. What’s wrong with me?)) In CodeBlocks all tests works perfectly. Looks like in validators I have same “Timeout:…”. HELP!!!
