# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
55478873 |
Practice:
McDic |
1182D
- 50
|
GNU C++17
|
Accepted
|
234 ms
|
21864 KB
|
2019-06-12 06:14:51 |
2019-06-17 13:32:53 |
|
#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;
}
Click to see test details