Baekjoon 15591번 MooTube (Silver)

문제

https://www.acmicpc.net/problem/15591

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int usado[5001][5001];
int visited[5001];
vector<int> adj[5001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, Q;
    cin >> N >> Q;
    memset(usado, 0, sizeof(usado));
    int p, q, r;
    for(int i = 0; i < N-1; i++){
        cin >> p >> q >> r;
        usado[p][q] = r;
        usado[q][p] = r;
        adj[p].push_back(q);
        adj[q].push_back(p);
    }
    int k, v;
    for(int i = 0; i < Q; i++){
        cin >> k >> v;
        int cnt = 0;
        memset(visited, 0, sizeof(visited));
        queue<int> q;
        q.push(v);
        visited[v] = 1;
        while(!q.empty()){
            int here = q.front();
            q.pop();
            for(int i = 0; i < adj[here].size(); i++){
                int next = adj[here][i];
                if(usado[here][next] < k) continue;
                if(!visited[next]){
                    cnt++;
                    q.push(next);
                    visited[next] = 1;
                }
            }
        }
        cout << cnt << "\n";
    }
    return 0;
}

미리 USADO 를 모두 구해놓으면 시간초과가 난다.

USADO 는 구하려는 두 쌍 사이의 모든 USADO 중 최소값이다. USADO 가 k 이상인 동영상의 개수를 구하는 것이 목적이므로, k 미만인 USADO 가 탐색 중 한번이라도 등장하였다면 그 이후의 동영상들은 k 이상의 값을 가질 수 없다는 뜻이므로 더 이상 탐색할 필요가 없게 된다.

k값과 동영상의 번호(v)가 주어지면 v를 기준으로 USADO 가 k 이상인 경로에 대해서만 탐색을 진행하면 시간초과가 나지 않게 된다.