[USACO] 백준 15591 - MooTube (Silver)

www.acmicpc.net/problem/15591

 

N, Q <= 5000 이므로

 

$O(NQ)$ 의 시간복잡도를 가진 솔루션으로 통과시킬 수 있고, 가장 간단한 구현은 각 쿼리마다 BFS를 돌려주는 것이다.

 

쿼리마다 BFS를 수행하면서 몇개의 동영상이 조건을 만족하는지 찾아주면 된다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
using pii = pair<int, int>;
 
bool visit[5001];
 
int query(vector<vector<pii>> &adj, int start, int relevance);
 
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, q;
    cin >> n >> q;
 
    vector<vector<pii>> al(n + 1);
 
    for (int i = 0; i < n - 1; ++i)
    {
        int go, to, val;
        cin >> go >> to >> val;
        al[go].push_back({to, val});
        al[to].push_back({go, val});
    }
 
    while (q--)
    {
        int k, from;
        cin >> k >> from;
        cout << query(al, from, k) << '\n';
    }
}
 
int query(vector<vector<pii>> &adj, int start, int relevance)
{
    int ret = 0;
 
    memset(visit, 0, sizeof visit);
    queue<pii> q;
    q.push({start, 1e9 + 20});
 
    while (q.size())
    {
        auto cur = q.front();
        visit[cur.first] = true;
        q.pop();
        
        if (cur.second < relevance)
            continue;
 
        for (auto t : adj[cur.first])
        {
            if (visit[t.first])
                continue;
            
            int rele = min(cur.second, t.second);
            if (rele >= relevance)
                ++ret;
            
            q.push({t.first, rele});
        }
    }
 
    return ret;
}