oj.uz

Submission #270462

# Submission time Handle Problem Language Result Execution time Memory
270462 2020-08-17T16:08:39 Z usuyus Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 24 ms 384 KB 
#include <bits/stdc++.h>
#define N 1001
using namespace std;

vector<int> tree[N], ord, temp;

int query(vector<int> islands);

void dfs(int node, int parent) {
	ord.push_back(node);
	for (int child : tree[node]) {
		if (child != parent) dfs(child, node);
	}
}

int findEgg(int n, vector<pair<int,int>> edges) {
	ord.clear();
	for (int i=1; i<=n; i++) tree[i].clear();

	for (int i=0; i<n-1; i++) {
		int a=edges[i].first, b=edges[i].second;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	dfs(1, 0);

	int l=1, r=n;
	while (l<r) {
		int m=(l+r)/2;
		temp.clear();
		temp.insert(temp.end(), ord.begin(), ord.begin()+m);
		
		int res = query(temp);
		if (res) r = m;
		else l=m+1;
	}

	return ord[l-1];
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Number of queries: 8
2 Correct 13 ms 384 KB Number of queries: 9
3 Correct 24 ms 384 KB Number of queries: 9
4 Correct 16 ms 384 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 384 KB Number of queries: 9
2 Correct 16 ms 384 KB Number of queries: 9
3 Correct 18 ms 384 KB Number of queries: 9
4 Correct 18 ms 384 KB Number of queries: 9