oj.uz

Submission #376333

# Submission time Handle Problem Language Result Execution time Memory
376333 2021-03-11T09:01:17 Z mosiashvililuka Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 35 ms 748 KB 
#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

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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Number of queries: 4
2 Correct 1 ms 364 KB Number of queries: 4
3 Correct 2 ms 364 KB Number of queries: 4
4 Correct 1 ms 364 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 492 KB Number of queries: 8
2 Correct 20 ms 620 KB Number of queries: 9
3 Correct 35 ms 736 KB Number of queries: 9
4 Correct 25 ms 648 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 736 KB Number of queries: 9
2 Correct 33 ms 748 KB Number of queries: 9
3 Correct 32 ms 748 KB Number of queries: 9
4 Correct 35 ms 620 KB Number of queries: 9