oj.uz

Submission #389297

# Submission time Handle Problem Language Result Execution time Memory
389297 2021-04-14T02:23:27 Z 8e7 Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 26 ms 580 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include "grader.h"
#define ll long long
#define maxn 550
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#define pii pair<int, int>
using namespace std;
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//template<lcass T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//find by order, order of key
namespace{
	vector<int> adj[maxn];
	vector<int> que;
	bool found[maxn];
	bool poss[maxn], cost[maxn];
}

void dfs(int n, int par, int &num) {
	if (num == 0) return;
	num -= cost[n];
	found[n] = 1;
	que.push_back(n);
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n, num);
		}
	}
}
int findEgg(int n, vector < pair < int, int > > bridges) {
	for (int i = 1;i <= n;i++) poss[i] = 1, cost[i] = 1, adj[i].clear();
	for (auto ed:bridges) {
		adj[ed.ff].push_back(ed.ss);
		adj[ed.ss].push_back(ed.ff);
	}
	int cur = n;
	while (true) {
		if (cur == 1) {
			for (int i = 1;i <= n;i++) {
				if (poss[i]) return i;
			}
			break;
		}
		for (int i = 1;i <= n;i++) found[i] = 0;
		que.clear();
		int num = cur / 2;
		cur -= num;
		dfs(1, 0, num);
		//cout << endl;
		int val = query(que);
		if (val) {
			for (int i = 1;i <= n;i++) {
				if (!found[i]) cost[i] = 0, poss[i] = 0;
			}
		} else {
			for (int i = 1;i <= n;i++) {
				if (found[i]) cost[i] = 0, poss[i] = 0;
			}
		}
	}
	return -1;
}
/*
5
1 2
1 3
2 4
3 5
5
1 2 3 4 5
 */

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Number of queries: 8
2 Correct 19 ms 328 KB Number of queries: 9
3 Correct 25 ms 580 KB Number of queries: 9
4 Correct 24 ms 448 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 372 KB Number of queries: 9
2 Correct 21 ms 344 KB Number of queries: 9
3 Correct 25 ms 360 KB Number of queries: 9
4 Correct 21 ms 332 KB Number of queries: 9