oj.uz

Submission #762648

# Submission time Handle Problem Language Result Execution time Memory
762648 2023-06-21T15:23:05 Z salmon Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 31 ms 568 KB 
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;


int findEgg (int N, vector <pair<int,int>> bridges){
    set<int> notdone;
    queue<int> q;
    bool visited[1100];
	set<int> adjlst[1100];
	vector<int> quer;
	int goal;

    for(int i = 1; i <= N; i++){
		visited[i] = false;
		notdone.insert(i);
	}

	for(int i = 0; i <  N - 1; i++){
		adjlst[bridges[i].first].insert(bridges[i].second);
		adjlst[bridges[i].second].insert(bridges[i].first);
	}

	while(notdone.size() != 1){
		int sise = notdone.size();
		goal = sise/2;

		for(auto i : notdone){
			bool flag = false;

			if(sise != N){
				for(int j : adjlst[i]){
					if(visited[j]){
						flag = true;
						break;
					}
				}
			}
			else{
				flag = true;
			}

			if(flag){
				q.push(i);
				while(!q.empty()){
					int i = q.front();
					q.pop();
					if(visited[i]) continue;
					if(goal == 0) continue;
					visited[i] = true;

					goal--;

					quer.push_back(i);

					for(int j : adjlst[i]){
						q.push(j);
					}
				}
			}
		}

		if(goal != 0){
			goal = goal / (goal - goal);
		}

		/*printf("q: ");
		for(auto i : quer){
			printf("%d ",i);
		}
		printf("\n");*/

		int con = quer.size();

		int ans = query(quer);

		if(ans == -1) return 10;

        if(con < sise/2){
            con = 1/ (con - con);
        }

		if(ans){
			for(int i = 1; i <= sise/2; i++){
				notdone.erase(quer[con - i]);
			}
			for(auto i : notdone){
				N--;
				visited[i] = false;
				for(int j : adjlst[i]){
					adjlst[j].erase(i);
				}
				adjlst[i].clear();
			}
			notdone.clear();
			for(int i = 1; i <= sise/2; i++){
				//printf("%d ",quer[i]);
				notdone.insert(quer[con - i]);
				visited[quer[con - i]] = false;
				quer.pop_back();
			}
		}
		else{
			for(int i = 1; i <= sise/2; i++){
				notdone.erase(quer[con - i]);
			}
		}

		/*for(auto i : notdone){
			printf("%d ",i);
		}
		printf("\n");*/
	}

	return (*notdone.begin());
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:64:16: warning: division by zero [-Wdiv-by-zero]
   64 |    goal = goal / (goal - goal);
      |           ~~~~~^~~~~~~~~~~~~~~
eastereggs.cpp:80:20: warning: division by zero [-Wdiv-by-zero]
   80 |             con = 1/ (con - con);
      |                   ~^~~~~~~~~~~~~

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 336 KB Number of queries: 8
2 Correct 18 ms 424 KB Number of queries: 9
3 Correct 31 ms 568 KB Number of queries: 9
4 Correct 22 ms 448 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 436 KB Number of queries: 9
2 Correct 29 ms 444 KB Number of queries: 9
3 Correct 23 ms 448 KB Number of queries: 9
4 Correct 22 ms 440 KB Number of queries: 9