Submission #385708

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
385708	2021-04-04T19:06:15 Z	Iwanttobreakfree	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	5 ms	748 KB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> c;
void conexa(vector<int>& v,vector<vector<int> >& cone,int raiz,int cont,vector<bool>& visto){
	visto[raiz]=true;
	for(int x: cone[raiz]){
		if(v.size()==cont){
			c=v;
			return;
		}
		if(!visto[x]){
			v.push_back(x+1);
			c=v;
			conexa(v,cone,x,cont,visto);
		}
	}
}
int findEgg (int N, vector < pair < int, int > > bridges){
	vector<vector<int> > cone(N,vector<int>());
	for(int i=0;i<N-1;i++){
		cone[bridges[i].first-1].push_back(bridges[i].second-1);
		cone[bridges[i].second-1].push_back(bridges[i].first-1);
	}
	int raiz,sol;
	vector<int> v;
	vector<bool> posi(N,true);
	int cont=N/2;
	while(cont>1){
		v.clear();
		for(int i=0;i<N;i++){
			if(posi[i]){
				raiz=i;
				break;
			}
		}
		vector<bool> visto(N,false);
		conexa(v,cone,raiz,cont,visto);
		v=c;
		if(query(v)){
			set<int> s;
			for(int i=0;i<v.size();i++)s.insert(v[i]-1);
			for(int i=0;i<N;i++){
				if(s.find(i)==s.end())posi[i]=false;
			}
			sol=v[0]-1;
			cone[v[0]-1].clear();
			posi[v[0]-1]=false;
			cont/=2;
		}
		else {
			for(int i=0;i<v.size();i++)posi[v[i]-1]=false;
		}
	}
    return sol;
}

Compilation message

eastereggs.cpp: In function 'void conexa(std::vector<int>&, std::vector<std::vector<int> >&, int, int, std::vector<bool>&)':
eastereggs.cpp:8:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
    8 |   if(v.size()==cont){
      |      ~~~~~~~~^~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for(int i=0;i<v.size();i++)s.insert(v[i]-1);
      |                ~^~~~~~~~~
eastereggs.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    for(int i=0;i<v.size();i++)posi[v[i]-1]=false;
      |                ~^~~~~~~~~
eastereggs.cpp:55:12: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |     return sol;
      |            ^~~
eastereggs.cpp:38:9: warning: 'raiz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |   conexa(v,cone,raiz,cont,visto);
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	492 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	2 ms	492 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	5 ms	748 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-