Submission #67735

#	Time	Username	Problem	Language	Result	Execution time	Memory
67735		quoriess	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	10 ms	1624 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;
const int MAXN=520;
vector<int> adj[MAXN];
bool cmarked[MAXN],dfsvisited[MAXN];
int sizes[MAXN];
vector<int> subtrees[MAXN];
void dfs(int node,int parent){
	int sm=1;
	subtrees[node].push_back(node);
	for (vector<int>::iterator it = adj[node].begin(); it !=adj[node].end() ; it++)
	{
		if(*it==parent||cmarked[*it] || dfsvisited[*it])continue;
		dfs(*it,node);
		sm+=sizes[*it];
	}
	sizes[node]=sm;
}
int noofchild[MAXN];
vector<int> reelchild[MAXN];
int tsa=0;
void subtreedfs(int node,int parent){
	subtrees[node].push_back(node);
	for (vector<int>::iterator it = adj[node].begin(); it !=adj[node].end() ; it++)
	{
		if(*it==parent||cmarked[*it])continue;
		reelchild[node].push_back(*it);
		subtreedfs(*it,node);
		noofchild[node]++;
		for(vector<int>::iterator it2=subtrees[*it].begin();it2!=subtrees[*it].end();it2++){
			subtrees[node].push_back(*it2);
		}
	}
}
int getcentroidhelper(int node,int parent,int sayi){
	bool iscntr=true;
	int heaviest=-1;
	for (vector<int>::iterator it = adj[node].begin(); it!=adj[node].end() ; it++)
	{
		if(*it==parent || cmarked[*it])continue;
		if(sizes[*it]>sayi/2)
			iscntr=false;
		if(heaviest==-1||sizes[*it]>sizes[heaviest])heaviest=*it;
	}
	int snc=0;
	if(iscntr && sayi-sizes[node]<=sayi/2)
		snc= node;
	else snc= getcentroidhelper(heaviest,node,sayi);
	cmarked[snc]=true;
	return snc;
}
int getcentroid(int node){
	dfs(node,-1);
	if(sizes[node]<=2)return  node;
	int cikan= getcentroidhelper(node,-1,sizes[node]);
	return cikan;
}
int findEgg (int N, vector < pair < int, int > > bridges)
{

	for(int i=1;i<=N;i++){
		subtrees[i].clear();
		noofchild[i]=0;
		reelchild[i].clear();
		adj[i].clear();
		cmarked[i]=false;
		dfsvisited[i]=false;
		sizes[i]=0;
	}
	for(int i=0;i<(int)bridges.size();i++){
		adj[bridges[i].first].push_back(bridges[i].second);
		adj[bridges[i].second].push_back(bridges[i].first);
	}
	/*
3
1 2
1 3
3
1
2
3 

16
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16



 * */
	int nd=1;
/*
16
1 2
2 3
1 4
4 5
5 6
5 7
7 8
8 9
9 10
8 11
10 12
4 13
4 14
4 15
1 16 
 * */
 
	while(true){
		int centro=getcentroid(nd);
		//cout << centro<<"\n";
		for(int i=1;i<=N;i++){
			subtrees[i].clear();
			noofchild[i]=0;
			reelchild[i].clear();
		}
		//cout <<"clear"<<"\n";
		if(sizes[centro]==1)return centro;
		vector<int> a;
		a.push_back(centro);
		if(query(a))return centro;
		subtreedfs(centro,-1);
		
		if(sizes[centro]==2)return reelchild[centro][0];
		for(int i=0;i<(int)reelchild[centro].size();i++){
			//cout << reelchild[centro][i]<<" ";
		}
		//cout <<"\n";
		int low=0,high=noofchild[centro]-1;
		int mid=(low+high)/2;
		int sol=-1;
		while(low<=high){
			mid=(low+high)/2;
			vector<int> sorgula;
			//cout << "low: "<<low<<" high: "<<high<<" mid: "<<mid<<"\n";
			//cout << "sorguluyor: \n";
			sorgula.push_back(centro);
			/*if((low==noofchild[centro]-1 || high==0) && sol==-1){
				sol= mid;
				break;
			}*/
			for(int i=0;i<=mid;i++){
				//cout << "child: "<<reelchild[centro][i]<<"\n";
				for(int j=0;j<(int)subtrees[reelchild[centro][i]].size();j++){
					sorgula.push_back(subtrees[reelchild[centro][i]][j]);
					//cout << sorgula[sorgula.size()-1]<<" ";
				}
				//cout<<"\n";
			}
			if(query(sorgula)){
				//cout << "sorgu doğru: "<<"\n";
				high=mid-1;
				sol=mid;
			}
			else{
				//cout << "sorgu yanlış\n";
				low=mid+1;
			}
		}
		if(sol==-1)return centro;
		nd=reelchild[centro][sol];

	}
	return -1;
}

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20