oj.uz

Submission #334433

# Submission time Handle Problem Language Result Execution time Memory
334433 2020-12-09T06:43:56 Z limabeans Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 22 ms 492 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;



vector<int> g[600];
vector<int> w;


int egg;

/*
int query(vector<int> a) {
    for (int x: a) {
	if (x==egg) return 1;
    }
    return 0;
    }*/


void dfs(int at, int p) {
    w.push_back(at);
    for (int to: g[at]) {
	if (to == p) continue;
	dfs(to, at);
    }
}

int findEgg (int n, vector < pair < int, int > > edges) {
    for (int i=0; i<=n; i++) {
	g[i].clear();
    }
    for (auto ed: edges) {
	int u = ed.first;
	int v = ed.second;
	g[u].push_back(v);
	g[v].push_back(u);
    }



    w.clear();
    dfs(1,0);

    assert((int)w.size()==n);


    int lo = -1;
    int hi = n-1;
    while (hi-lo>1) {
	int mid = (lo+hi)/2;
	vector<int> v(w.begin(),w.begin()+mid+1);
	
	if (query(v)) {
	    hi = mid;
	} else {
	    lo = mid;
	}
    }

    return w[hi];
}

/*
int main() {
    int n;
    cin>>n;
    vector<pair<int,int>> edges(n-1);
    for (int i=0; i<n-1; i++) {
	cin>>edges[i].first>>edges[i].second;
    }

    int q;
    cin>>q;
    while (q--) {
	cin>>egg;
	int res = findEgg(n,edges);
	cout<<egg<<" vs "<<res<<endl;
	assert(egg==res);
    }
}
*/

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 364 KB Number of queries: 8
2 Correct 14 ms 364 KB Number of queries: 9
3 Correct 20 ms 364 KB Number of queries: 9
4 Correct 22 ms 364 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 364 KB Number of queries: 9
2 Correct 17 ms 364 KB Number of queries: 9
3 Correct 20 ms 492 KB Number of queries: 9
4 Correct 18 ms 364 KB Number of queries: 9