Solution for CCC '18 J5 - Choose your own path in C++


April 9, 2020 0.226740 seconds C++
#include <bits/stdc++.h>
#include <iostream>
#include <set>
#include <map>
#include <memory>
#include <stack>
#include <queue>

using namespace std;


typedef struct node{
	int data;
	vector<shared_ptr<struct node>> children;
	
}node_t; 


int shortest_path(vector<shared_ptr<node_t>> nodes, int level){
	
	level++;
	vector<shared_ptr<node_t>> childNodes;
	
	for(auto node : nodes){
		if(node->children.size() == 0){
			
			return level;
		}else{
			for(auto a: node->children){
				childNodes.push_back(a);
			}
			
		}
		
	}
	return shortest_path(childNodes, level);
}

void getReachablePages(shared_ptr<node_t> node, set<int>& pages){
	
	if(pages.find(node->data) == pages.end()){
		pages.insert(node->data);
		for(auto a : node-> children){
			getReachablePages(a, pages);
		}
	}
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	map <int, shared_ptr<node_t>> pageMap;
	for(int i = 0; i < n; i++){
		pageMap[i + 1] = make_unique<node_t>();
		pageMap[i + 1]->data = i + 1;
	}
	
	for(int i = 1; i <= n; i++){
		
		int num = 0;
		cin >> num;
		for(int j = 0; j < num; j++){
			int page = 0;
			cin >> page;
			pageMap[i]-> children.push_back(pageMap[page]);
		}
		
	}
	
	set<int> pages;
	getReachablePages(pageMap[1], pages);
	if(pages.size() == n){
		cout << "Y\n";
	}else{
		cout << "N\n";
	}
	
	int level = 0;
	vector<shared_ptr<node_t>> nodesToCheck;
	nodesToCheck.push_back(pageMap[1]);
	cout << shortest_path(nodesToCheck, level) << "\n";
	
	return 0;
}

Editorial


No editorial for this problem. :(

Original Problem


You can view the original page for this problem on the DMOJ.