oj.uz

Submission #110505

# Submission time Handle Problem Language Result Execution time Memory
110505 2019-05-11T04:59:35 Z tjd229 Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 27 ms 384 KB 
#include <bits/stdc++.h>
//#include<vector>
//#include<queue>
//#include <set>
#include "grader.h"
#define pii pair<int,int>
using namespace std;
int p[513],d[513];
vector<int> order;
void dfs(int x,int from,vector<int> *edge) {
	order.push_back(x);
	p[x] = from;
	for (auto nxt : edge[x]) {
		if (nxt != from) {
			d[nxt] = d[x] + 1;
			dfs(nxt, x, edge);
		}
	}
}
void make_beauty(vector<int> &tree) {
	set<pii > st;//depth,x
	for (auto x : tree) {
		st.insert({-d[x],x});
	}
	while (st.size() > 1) {
		int depth = st.begin()->first;
		while (st.begin()->first ==depth) {
			int par = p[st.begin()->second];
			if (st.find({ -d[par],par }) == st.end()) {
				tree.push_back(par);
				st.insert({ -d[par],par });
			}
			st.erase(st.begin());
		}
	}
}
int ask(int l,int r) {
	vector<int> v;
	for (int i = l; i <= r; ++i) v.push_back(order[i]);
	//
	make_beauty(v);
	return query(v);
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
	vector<int> edge[513]; order.clear();
	for (auto p : bridges) {
		int u = p.first, v = p.second;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	d[1] = 0;
	dfs(1, -1, edge);
	int l = 0, r = N-1;
	int k = -1;
	while (l <= r) {
		if (l == r && l == N - 1) {
			k = N - 1;
			break;
		}
		int m = (l + r)>>1;
		if (ask(l, m)) k=m,r = m-1;
		else l = m + 1;
	}
    return order[k];
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Number of queries: 8
2 Correct 14 ms 256 KB Number of queries: 9
3 Correct 27 ms 256 KB Number of queries: 9
4 Correct 16 ms 372 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 384 KB Number of queries: 9
2 Correct 22 ms 256 KB Number of queries: 9
3 Correct 22 ms 256 KB Number of queries: 9
4 Correct 18 ms 376 KB Number of queries: 9