oj.uz

Submission #80831

# Submission time Handle Problem Language Result Execution time Memory
80831 2018-10-22T12:39:12 Z farukkastamonuda Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 22 ms 624 KB 
#include <bits/stdc++.h>
#include "grader.h"
#define fi first
#define se second
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define li 555
#define mp make_pair
#define pb push_back
using namespace std;
int cur,mark[li], now;
vector<int> v[li], send;
bool init;
void dfs(int node,int ata){
	if(now == cur/2) return ;
	now += (! mark[node]);
	send.pb(node);
	for(int i = 0;i < (int)v[node].size(); i++){
		int go = v[node][i];
		if(go != ata) dfs(go,node);
	}
}
int findEgg(int N, vector< pair<int, int> > bridges){
	for(int i=1;i<=N;i++) mark[i]=0;
	if(!init) {
		for(int i = 0; i < N - 1; i++){
			int x = bridges[i].fi;
			int y = bridges[i].se;
			v[x].pb(y);
			v[y].pb(x);
		}
		init=true;
	}
	cur = N;
	while(cur > 1){
		now = 0;
		dfs(1, 0);
		if(query(send) == 1){
			cur /= 2;
			for(int i = 1;i <= N ; i++){
				mark[i]++;
			}
			for(int i = 0;i < (int)send.size(); i++){
				mark[send[i]]--;
			}
		}
		else{
			cur = cur - cur / 2;
			for(int i = 0;i < (int)send.size(); i++){
				mark[send[i]]=1;
			}
		}
		send.clear();
	}
	for(int i = 1;i <= N; i++){
		if(mark[i] == 0) return i;
	}
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:59: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 2 ms 248 KB Number of queries: 4
2 Correct 3 ms 324 KB Number of queries: 4
3 Correct 2 ms 400 KB Number of queries: 4
4 Correct 2 ms 452 KB Number of queries: 4

Subtask #2
40.0 / 40.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 624 KB Number of queries: 9
2 Correct 22 ms 624 KB Number of queries: 9
3 Correct 19 ms 624 KB Number of queries: 9
4 Correct 21 ms 624 KB Number of queries: 9