General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
55478873 Practice:
McDic
1182D - 50 C++17 (GCC 7-32) Accepted 234 ms 21864 KB 2019-06-12 06:14:51 2019-06-17 13:32:53
→ Source
#include <stdio.h>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>

// Graph attributes
typedef std::vector<std::set<int>> EDGE;
int v;
std::vector<bool> isInner;
EDGE edges, inneredges;

// Validation
bool validate(int root){
	
	//printf("Validating for %d\n", root);
	std::vector<bool> visited(v+1, false);
	std::vector<int> nowlook = {root};
	while(!nowlook.empty()){
		std::set<int> degrees;
		std::vector<int> nextlook;
		for(auto now: nowlook) visited[now] = true;
		for(auto now: nowlook){
			for(auto next: edges[now]){
				if(!visited[next]){
					nextlook.push_back(next);
					degrees.insert(edges[next].size());
					if(degrees.size() >= 2) return false;
				}
			}
		} nowlook = nextlook;
	} return true;
}

// Calculate distances for directly reachable nodes. -1 for not set.
void directDistanceCalculation(int now, std::vector<int> &distance){
	for(auto next: edges[now]){
		if(distance[next] == -1 && edges[next].size() <= 2){
			distance[next] = distance[now]+1;
			directDistanceCalculation(next, distance);
		}
	}
}

int main(void){
	
	// Get input and construct tree
	scanf("%d", &v); 
	edges.resize(v+1);
	isInner.resize(v+1, true);
	for(int i=1; i<v; i++){
		int u1, u2; scanf("%d %d", &u1, &u2);
		edges[u1].insert(u2);
		edges[u2].insert(u1);
	} inneredges = edges;
	
	// Construct inner tree
	//printf("Constructing inner tree:\n");
	for(int start=1; start<=v; start++){
		if(edges[start].size() == 1 && inneredges[start].size() == 1){
			int now = start;
			while(edges[now].size() <= 2 && inneredges[now].size() == 1){
				//printf("Removing %d\n", now);
				int next = *(inneredges[now].begin());
				inneredges[now].clear();
				inneredges[next].erase(now);
				isInner[now] = false;
				now = next;
			}
		}
	}
	
	// Corner case: No inner tree => See leaf
	//printf("Let's see if this is corner case\n");
	int innervertices = 0;
	std::vector<int> leaves;
	for(int u=1; u<=v; u++){
		if(isInner[u]) innervertices++;
		if(edges[u].size() == 1) leaves.push_back(u);
	}
	if(innervertices == 0){
		//printf("ok no inner\n");
		for(auto leaf: leaves){
			if(validate(leaf)){
				printf("%d\n", leaf);
				return 0;
			}
		}
		throw "???";
	}
	
	// Collapse inner tree
	//printf("Let's collapse inner tree\n");
	std::vector<bool> collapseVisited(v+1, false);
	std::vector<int> nowlook;
	for(int u=1; u<=v; u++) if(isInner[u] && inneredges[u].size() <= 1) nowlook.push_back(u);
	while(nowlook.size() >= 2){
		std::set<int> nextlook;
		for(auto now: nowlook) collapseVisited[now] = true;
		for(auto now: nowlook) for(auto next: inneredges[now]) if(!collapseVisited[next]) nextlook.insert(next);
		nowlook.clear();
		for(auto next: nextlook) nowlook.push_back(next);
	}
	
	// Corner case 2: No semitop
	if(nowlook.empty()){
		printf("-1\n"); 
		return 0;
	}
	
	// Semitop validation
	int semitop = nowlook[0];
	//printf("Ok semitop is %d\n", semitop);
	if(validate(semitop)){
		printf("%d\n", semitop);
		return 0;
	}
	
	// Calculate distances for directly reachable leaves
	std::vector<int> dirDist(v+1, -1);
	dirDist[semitop] = 0;
	directDistanceCalculation(semitop, dirDist);
	std::vector<std::pair<int, int>> directLeaves;
	for(int u=1; u<=v; u++){
		if(edges[u].size() == 1 && dirDist[u] != -1) 
			directLeaves.push_back({dirDist[u], u});
	} std::sort(directLeaves.begin(), directLeaves.end());
	
	// Validate for the furthest leaf and the closest leaf
	if(!directLeaves.empty()){
		int closestLeaf = directLeaves.front().second;
		int furthestLeaf = directLeaves.back().second;
		if(validate(closestLeaf)){
			printf("%d\n", closestLeaf);
			return 0;
		}
		else if(validate(furthestLeaf)){
			printf("%d\n", furthestLeaf);
			return 0;
		}
	}
	printf("-1\n");
	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details