oj.uz

Submission #272027

# Submission time Handle Problem Language Result Execution time Memory
272027 2020-08-18T08:23:05 Z erkam Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 75 ms 436 KB 
#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

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

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 384 KB Number of queries: 8
2 Correct 43 ms 384 KB Number of queries: 9
3 Correct 75 ms 384 KB Number of queries: 9
4 Correct 65 ms 384 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 436 KB Number of queries: 9
2 Correct 61 ms 384 KB Number of queries: 9
3 Correct 61 ms 384 KB Number of queries: 9
4 Correct 74 ms 384 KB Number of queries: 9