oj.uz

Submission #882266

# Submission time Handle Problem Language Result Execution time Memory
882266 2023-12-02T21:11:26 Z gustavo_d Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 15 ms 1012 KB 
// https://oj.uz/problem/view/info1cup17_eastereggs > p150
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

int findEgg (int N, vector < pair < int, int > > bridges)
{
	vector<vector<int>> adj(N);
	vector<bool> vis(N, false);
	vector<int> always;
	for (pair<int,int> p : bridges) {
		adj[p.first-1].push_back(p.second-1);
		adj[p.second-1].push_back(p.first-1);
	}
	queue<pair<int,int>> visit; visit.push({0, 1}); vis[0] = true;
	vector<int> send;
	int n = N;
	while (!visit.empty()) {
		int v = visit.front().first;
		if (visit.front().second == 1) send.push_back(v+1);
		visit.pop();
		
		for (int viz : adj[v]) {
			if (!vis[viz]) {
				vis[viz] = true;
				visit.push({viz, 1});
			}
		}		
		
		if ((int)send.size() == (n+1)/2) {
			for (int i : send) always.push_back(i);
			int res = query(always);
			//for (int i : always) cout << i << ' ';
			//cout << send.size() << ' ' << res << endl;
			if ((int)send.size() == 1 and res == 1) {
				return send[0];
			}
			if (n - (int)send.size() == 1 and res == 0) {
				return visit.front().first + 1;
			}
			if (res == 0) {
				n -= (int)send.size();
			}
			else {
				for (int i : send) always.pop_back();
				n = (int)send.size();
				for (int i=0; i<N; i++) vis[i] = true;
				while (!visit.empty()) visit.pop();
				for (int i : send) {
					vis[i-1] = false;
				}
				for (int i : always) {
					visit.push({i-1, -1});
				}
				if (visit.empty()) {
					visit.push({0, 1});
					vis[0] = true;
				}
			}
			send.clear();
		}
	}
	return -1;
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:46:14: warning: unused variable 'i' [-Wunused-variable]
   46 |     for (int i : send) always.pop_back();
      |              ^

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 432 KB Number of queries: 4
2 Correct 1 ms 440 KB Number of queries: 4
3 Correct 1 ms 344 KB Number of queries: 4
4 Correct 0 ms 440 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 464 KB Number of queries: 8
2 Correct 9 ms 736 KB Number of queries: 9
3 Correct 15 ms 748 KB Number of queries: 9
4 Correct 12 ms 740 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 992 KB Number of queries: 9
2 Correct 13 ms 988 KB Number of queries: 9
3 Correct 13 ms 1012 KB Number of queries: 9
4 Correct 14 ms 748 KB Number of queries: 9