ZeroJudge B298: Refunds

Taiwanese food is really delicious, but recently there's been a food safety issue causing anxiety among people in Taiwan, leading to a wave of product returns. You happen to have bought a large quantity of mooncakes, and now you want to return them, but you're unsure which ones are problematic and which are not. Just then, a Taiwan manufacturer supply diagram drops from the sky. You know that some of these manufacturers have issues, and when one manufacturer has a problem, all downstream manufacturers are affected too. With this diagram, you can decide which mooncakes to return!

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line contains four positive integers N, M, L, Q (where N, L, Q <= 10000 and M <= 100000), where N represents the number of manufacturers (numbered from 1 to N).
The following M lines each contain two numbers, a and b, indicating that manufacturer a supplies materials to manufacturer b.
Following that, there are L lines, each containing a number x, indicating that the xth manufacturer has issues.
Following that, there are Q lines, each containing a number y, asking whether the yth manufacturer has issues.		For each query, if there are no issues, output "YA~~"; otherwise, output "TUIHUOOOOOO". Each query should be on a separate line.
5 3 1 2
1 2
1 3
3 4
3
2
4		YA~~
TUIHUOOOOOO

Thought Process

Record who are the downstream suppliers for each manufacturer. When receiving L problematic manufacturers, record all received manufacturers and their downstream suppliers using BFS. During Q inquiries, check if the inquired manufacturer has been recorded.

Sample Code－ZeroJudge B298: Refunds

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int problem[10001] = {}, walk[10001] = {};

vector<int> MAP[10001] = {};

void BFS(const vector<int>start) {
    if (start.size() == 0) return;
    vector<int>newStart;
    map<int, int>push;
    for (int i = 0; i<start.size(); i++) {
        const int num = start[i];
        walk[num]++;
        const vector<int> v = MAP[num];
        for (int j = 0; j<v.size(); j++) {
            const int vv = v[j];
            problem[vv]++;
            if (walk[vv] == 0 && push[vv] == 0) {
                push[vv]++;
                newStart.push_back(vv);
            }
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, M, L, Q;
    cin >> N >> M >> L >> Q;
    for (int i = 1; i<=N; i++) {
        problem[i] = 0;
        vector<int> tmp;
        MAP[i] = tmp;
        walk[i] = 0;
    }
    for (int i = 0; i<M; i++) {
        int a, b;
        cin >> a >> b;
        MAP[a].push_back(b);
    }
    for (int i = 0; i<L; i++) {
        int x;
        cin >> x;
        problem[x]++;
        vector<int>tmp;
        tmp.push_back(x);
        BFS(tmp);
    }
    for (int i = 0; i<Q; i++) {
        int y;
        cin >> y;
        if (problem[y] == 0) cout << "YA~~\n";
        else cout << "TUIHUOOOOOO\n";
    }
}

//ZeroJudge B298
//Dr. SeanXD
Tags

Related Posts

Comments