oj.uz

Submission #98329

# Submission time Handle Problem Language Result Execution time Memory
98329 2019-02-22T12:11:55 Z tmk Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 31 ms 384 KB 
#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
#ifndef d
#define d(...)
#endif
#define st first
#define nd second
#define pb push_back
#define siz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
typedef long long LL;
typedef long double LD;
constexpr int INF=1e9+7;
constexpr LL INFL=1e18;
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

constexpr int maxn = 520;

int n;
vector<int> G[maxn];
bool vis[maxn];

vector<int> get_bfs_order() {
	vector<int> ret;
	ret.push_back(1);
	vis[1] = true;
	for(int i=0; i<siz(ret); i++) {
		auto w = ret[i];
		for(auto v:G[w])
			if(not vis[v]) {
				vis[v] = true;
				ret.push_back(v);
			}
	}
	
	return ret;
}

int findEgg(int _n, vector<pair<int, int>> edges) {
	n = _n;
	for(int i=1; i<=n; i++)
		G[i].clear(), vis[i] = false;
	for(auto& e:edges) {
		G[e.st].push_back(e.nd);
		G[e.nd].push_back(e.st);
	}
	
	auto&& v = get_bfs_order();
	int l = 1, r = n;
	while(l < r) {
		auto s = (l+r) / 2;
		if(query(vector<int>(v.begin(), v.begin() + s)))
			r = s;
		else
			l = s + 1;
	}
	
	return v[l-1];
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
20.0 / 20.0

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