Submission #67660

#	Time	Username	Problem	Language	Result	Execution time	Memory
67660		quoriess	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	4 ms	904 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;
	//visited[node]=1;
	subtrees[node].push_back(node);
	for (vector<int>::iterator it = adj[node].begin(); it !=adj[node].end() ; it++)
	{
		//cout << "it: "<<*it<<"\n";
		if(*it==parent||cmarked[*it] || dfsvisited[*it])continue;
		//cout << "devamit"<<*it<<"\n";
		dfs(*it,node);
		sm+=sizes[*it];
	}
	sizes[node]=sm;
}
int noofchild[520];
vector<int> reelchild[520];
void subtreedfs(int node,int parent){
	subtrees[node].push_back(node);
	for (vector<int>::iterator it = adj[node].begin(); it !=adj[node].end() ; it++)
	{
		//cout << "it: "<<*it<<"\n";
		if(*it==parent||cmarked[*it])continue;
		//cout << "devamit"<<*it<<"\n";
		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;
	//cout << "cbaktı: "<<node<<"\n";
	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;
	//////cout << "cntroid: "<<snc<<"\n";
	else snc= getcentroidhelper(heaviest,node,sayi);
	cmarked[snc]=true;
	return snc;
}
int getcentroid(int node){
	////cout << "centroid araması: "<<node<<"\n";
	dfs(node,-1);
	if(sizes[node]<=2)return  node;
	//cout << "subtree size: "<< glsbtsizes[node]<<"\n";
	//cout << "ELAPSED: "<< (clock()*1.0-start)/CLOCKS_PER_SEC*1000<<" MS\n";
	//////cout << "dfs bitti: "<<"\n";
	int cikan= getcentroidhelper(node,-1,sizes[node]);
	////cout << "centroid buldu: "<<cikan<<"\n";
	return cikan;
}
char sonuclar[MAXN];
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 
	 * */
	int nd=1;
	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);
		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);
			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;
		else nd=reelchild[nd][mid];
	}
	return 0;
}

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