제출 #67665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67665		quoriess	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	3 ms	516 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;
	}
	return -1;
}

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