oj.uz

Submission #762188

# Submission time Handle Problem Language Result Execution time Memory
762188 2023-06-21T03:56:15 Z salmon Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 1 ms 592 KB 
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
bool visited[1100];
vector<int> adjlst[1100];
vector<int> quer;
int goal;
bool marked[1100];

void dfs(int i){
	if(visited[i]) return;
	if(goal == 0) return;
	visited[i] = true;
	
	goal--;
	
	quer.push_back(i);
	
	for(int j : adjlst[i]){
		marked[j] = true;
		dfs(j);
	}
}

int findEgg (int N, vector <pair<int,int>> bridges){
    set<int> notdone;
     
    for(int i = 1; i <= N; i++){
		visited[i] = false;
		adjlst[i].clear();
		marked[i] = false;
		notdone.insert(i);
	}
	
	quer.clear();
	
	for(int i = 0; i <  N - 1; i++){
		adjlst[bridges[i].first].push_back(bridges[i].second);
		adjlst[bridges[i].second].push_back(bridges[i].first);
	}
	
	marked[1] = true;
	
	while(notdone.size() != 1){
		int sise = notdone.size();
		goal = sise/2;
		
		for(auto i : notdone){
			if(marked[i]){
				dfs(i);
			}
		}
		
		/*printf("q: ");
		for(auto i : quer){
			printf("%d ",i);
		}
		printf("\n");*/
		
		int con = quer.size();
		
		if(query(quer)){
			notdone.clear();
			for(int i = quer.size() - 1; i > con - 1 - sise/2; i--){
				//printf("%d ",quer[i]);
				notdone.insert(quer[i]);
				visited[quer[i]] = false;
				quer.pop_back();
			}
		}
		else{
			for(int i = quer.size() - 1; i > con - 1 - sise/2; i--){
				notdone.erase(quer[i]);
			}
		}
		
		/*for(auto i : notdone){
			printf("%d ",i);
		}
		printf("\n");
		*/
		//return 1;
	}
	
	return (*notdone.begin());
}

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 464 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 464 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -