Submission #272027

#	Time	Username	Problem	Language	Result	Execution time	Memory
272027		erkam	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	75 ms	436 KiB

eastereggs

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include "grader.h"
#define endl "\n"
#define all(v) v.begin(),v.end()
#define st first
#define nd second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long lo;
string s;

// int query(vector<int> hehe){

// }

int findEgg(int n,vector<pair<int,int> > bridges){
	vector<int>v[n+5];
	bool h[n+5]={0};
	for(lo i=0;i<bridges.size();i++){
		v[bridges[i].st].pb(bridges[i].nd);
		v[bridges[i].nd].pb(bridges[i].st);
	}
	int N=n;
	while(true){
		if(N==1){
			for(lo i=1;i<=n;i++){
				if(h[i]==0) return i;
			}
		}
		queue<int>q;
		map<int,bool>sorgu;
		q.push(1);
		int say=0;
		while(say<N/2){
			int x=q.front();
			q.pop();
			sorgu[x]=1;
			if(h[x]==0)say++;
			for(int i=0;i<v[x].size();i++){
				if(sorgu.count(v[x][i])==0)q.push(v[x][i]);
			}
		}
		vector<int>sor;
		for(int i=1;i<=n;i++){
			if(sorgu.count(i))sor.pb(i);
		}
		int x=query(sor);
		for(int i=1;i<=n;i++){
			if(sorgu.count(i)!=x)h[i]=1;
		}
		if(x==0) N-=say;
		else N=say;
	}
}
 
// int main(){

// }

Compilation message (stderr)

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:30:14: warning: comparison of integer expressions of different signedness: 'lo' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(lo i=0;i<bridges.size();i++){
      |             ~^~~~~~~~~~~~~~~
eastereggs.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    for(int i=0;i<v[x].size();i++){
      |                ~^~~~~~~~~~~~
eastereggs.cpp:60:21: warning: comparison of integer expressions of different signedness: 'std::map<int, bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |    if(sorgu.count(i)!=x)h[i]=1;
      |       ~~~~~~~~~~~~~~^~~

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