USACO 2018 January Contest Silver Division - MooTube

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Given that the constraints are small, we can use a BFS for every query on the tree we construct to determine the number of vertexes which will be visited such that the weight of the edge is greater or equal to \(k\).

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000, MAXV = MAXN;

int main() {
    ifstream cin("mootube.in");
    ofstream cout("mootube.out");

    int n, q, v1, v2, r, i, k, v, node, numSuggested;

    cin >> n >> q;

    vector<vector<pair<int, int>>> goFromTo(n);
    for (i = 0; i < n - 1; i++) {
        cin >> v1 >> v2 >> r;

        v1--, v2--;
        goFromTo[v1].push_back({v2, r});
        goFromTo[v2].push_back({v1, r});
    }

    for (i = 0; i < q; i++) {
        cin >> k >> v;

        unordered_map<int, int> wasVisited;
        queue<int> qu;

        qu.push(v - 1);
        wasVisited[v - 1] = 1;
        numSuggested = 0;

        while (!qu.empty()) {
            nod = qu.front();
            qu.pop();

            for (auto travelNode : goFromTo[node]) {
                if (!wasVisited[travelNode.first] && travelNode.second >= k) {
                    ++numSuggested;
                    wasVisited[travelNode.first] = 1;
                    qu.push(travelNode.first);
                }
            }
        }

        cout << numSuggested << '\n';
    }

    return 0;
}