Submission #89006

#	Time	Username	Problem	Language	Result	Execution time	Memory
89006		gbutbaia	Triumphal arch (POI13_luk)	C++14	0 / 100	4 ms	820 KiB

luk

#include <iostream>
#include <vector>
#include <set>
#include <string>

using namespace std;


vector<vector<int>> tree(100);


int res(set<int> checked, int a) {
    int count = 0;
    for(unsigned int i = 0; i<tree[a].size(); i++) {
        if(checked.count(tree[a][i]) == 0) {count++;}
    }
    return count;
}


//Filters out only nonChecked ones
vector<int> getNonCheckedNeighborhood(set<int> checked, vector<int> depthLevel) {
	vector<int> result;
	for(int elem : depthLevel) {
		if(checked.count(elem) == 0) {result.push_back(elem);}
	}
	return result;
}


//for point= tree[i][j] do the following:
//For each element in nonCheckedNeighborhood
//count the size of nonCheckedNeightborhood, then go down

unsigned int prevResult = 0;

void findNumber(int point, set<int> &checked) {
    vector<int> N = getNonCheckedNeighborhood(checked, tree[point]); //NonChecked neighborhood
  //  cout << "Size: " << N.size() << endl;
    if(N.size() >prevResult) prevResult = N.size();
   // printVector(N);
    checked.insert(point);
    for(unsigned int i = 0; i < N.size(); i++) {
		findNumber(N[i], checked);
    }

}

int main(){    
    int n;
    cin >> n;
    
    for(int i =0; i < n-1; i++) {
        int a,b  = 0;
        cin >> a;
        cin >> b;
        //cout << a-1 << " " << b-1 << endl;
        tree[a-1].push_back(b-1);
        tree[b-1].push_back(a-1);
    }

    //Here tree is the folloiwg
    //tree[0] = {1,2,3}; tree[1] = {0}, tree[2] = {0,3,4,5}, tree[3] = {0}    
    set<int> checked = {};
    findNumber(0, checked);
    cout << prevResult<< endl;
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10