oj.uz

Submission #243029

# Submission time Handle Problem Language Result Execution time Memory
243029 2020-06-30T08:00:47 Z umk Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 31 ms 2920 KB 
#include<bits/stdc++.h>
#include "grader.h"

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

const int N = 1e5+5;
int ck[N], nw[N], cnt, cur, num;
vector <int> adj[N], ans;

void dfs(int u, int p){
	if (cur == num) return ;
	if (ck[u]) cur++;
	ans.pb(u);
	for (int i=0; i<(int)adj[u].size(); i++){
		int v = adj[u][i];
		if (v == p) continue;
		dfs(v, u);
	}
}

int findEgg(int n, vector <pair <int, int> > e){
	for (int i=1; i<=n; i++) ck[i] = 1;
	cnt = n;
	for (int i=1; i<=n; i++) adj[i].clear();
	for (int i=1; i<n; i++){
		adj[e[i-1].fi].pb(e[i-1].se);
		adj[e[i-1].se].pb(e[i-1].fi);
	} 
	while (cnt != 1){
		num = (cnt+1)>>1; cur = 0;
		ans.clear();
		dfs(1, 1);
		if (query(ans)){
			for (int i=1; i<=n; i++) nw[i] = 0;
			for (int i=0; i<(int)ans.size(); i++) nw[ans[i]] = ck[ans[i]];
			for (int i=1; i<=n; i++) ck[i] = nw[i];
			cnt = num;
		}
		else{
			for (int i=0; i<(int)ans.size(); i++) ck[ans[i]] = 0;
			cnt -= num;
		}
	}
	for (int i=1; i<=n; i++) if (ck[i]) return i;
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2688 KB Number of queries: 8
2 Correct 20 ms 2688 KB Number of queries: 9
3 Correct 24 ms 2688 KB Number of queries: 9
4 Correct 20 ms 2920 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2688 KB Number of queries: 9
2 Correct 31 ms 2688 KB Number of queries: 9
3 Correct 26 ms 2688 KB Number of queries: 9
4 Correct 27 ms 2688 KB Number of queries: 9