oj.uz

Submission #67665

# Submission time Handle Problem Language Result Execution time Memory
67665 2018-08-15T08:13:11 Z quoriess Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 3 ms 516 KB 
#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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB The found island is incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 440 KB The found island is incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 516 KB The found island is incorrect
2 Halted 0 ms 0 KB -