Submission #376333

#	Time	Username	Problem	Language	Result	Execution time	Memory
376333		mosiashvililuka	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	35 ms	748 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,K,fx[1009],cnt,bo[1009],kl;
vector <int> v[1009],vv;
void dfs(int q){
	vv.push_back(q);
	if(fx[q]==cnt){
		c++;
	}
	bo[q]=kl;
	if(c>=K/2+K%2){
		return;
	}
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if(bo[(*it)]==kl) continue;
		dfs((*it));
		if(c>=K/2+K%2){
			return;
		}
	}
}
int findEgg (int N, vector < pair < int, int > > br)
{
    //if (query ({1})) return 1;
    a=N;
    for(i=0; i<br.size(); i++){
    	v[br[i].first].push_back(br[i].second);
    	v[br[i].second].push_back(br[i].first);
	}
	cnt=1;K=a;
	for(i=1; i<=a; i++){
		fx[i]=1;
	}
    while(1){
    	//cout<<K<<endl;
    	if(K==1){
    		for(i=1; i<=a; i++){
    			if(fx[i]==cnt){
    				return i;
				}
			}
		}
    	kl++;c=0;vv.clear();
    	dfs(1);
    	zx=query(vv);
    	if(zx==0){
    		for(i=0; i<vv.size(); i++){
    			fx[vv[i]]=0;
			}
			K=K-c;
		}else{
			for(i=0; i<vv.size(); i++){
				if(fx[vv[i]]==cnt) fx[vv[i]]++;
			}
			K=c;
			cnt++;
		}
	}
//	return N;
}

Compilation message (stderr)

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(i=0; i<br.size(); i++){
      |              ~^~~~~~~~~~
eastereggs.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |       for(i=0; i<vv.size(); i++){
      |                ~^~~~~~~~~~
eastereggs.cpp:54:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for(i=0; i<vv.size(); i++){
      |             ~^~~~~~~~~~

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20