{"id":1115,"date":"2024-08-21T09:00:00","date_gmt":"2024-08-21T01:00:00","guid":{"rendered":"https:\/\/seanxd.com\/?p=1115"},"modified":"2024-07-16T23:38:11","modified_gmt":"2024-07-16T15:38:11","slug":"zerojudge-b298","status":"publish","type":"post","link":"https:\/\/seanxd.com\/en\/zerojudge-b298\/","title":{"rendered":"ZeroJudge B298: Refunds"},"content":{"rendered":"\n\n\n

\u53f0\u7063\u7684\u6771\u897f\u771f\u7684\u8d85\u597d\u5403\uff0c\u4f46\u662f\u6700\u8fd1\u7206\u767c\u4e86\u98df\u5b89\u554f\u984c\uff0c\u5bb3\u5f97\u81fa\u7063\u4eba\u5fc3\u60f6\u60f6\uff0c\u5f15\u767c\u9000\u8ca8\u6f6e\u3002\u4f60\u5bb6\u88e1\u525b\u597d\u8cb7\u4e86\u4e00\u5927\u5806\u6708\u9905\uff0c\u4f60\u60f3\u8981\u62ff\u53bb\u9000\u8ca8\uff0c\u4f46\u662f\u53c8\u4e0d\u77e5\u9053\u54ea\u4e9b\u6709\u554f\u984c\u54ea\u4e9b\u6c92\u554f\u984c\u3002\u9019\u6642\u5929\u4e0a\u6389\u4e0b\u4f86\u4e00\u5f35\u53f0\u7063\u5ee0\u5546\u539f\u6599\u4f9b\u61c9\u5716\uff0c\u4f60\u53ea\u77e5\u9053\u5176\u4e2d\u67d0\u5e7e\u5bb6\u662f\u6709\u554f\u984c\u7684\uff0c\u7576\u4e00\u5bb6\u5ee0\u5546\u6709\u554f\u984c\uff0c\u90a3\u5b83\u7684\u4e0b\u6e38\u5ee0\u5546\u4e5f\u5168\u90fd\u6709\u554f\u984c\u3002\u6709\u4e86\u9019\u5f35\u5716\uff0c\u4f60\u5c31\u53ef\u4ee5\u6c7a\u5b9a\u8981\u628a\u54ea\u4e9b\u6708\u9905\u9000\u8ca8\u4e86!<\/p>\n\n\n\n

\u7bc4\u4f8b\u6e2c\u8cc7<\/h2>\n\n\n\n
\u7bc4\u4f8b\u8f38\u5165<\/th>\u7bc4\u4f8b\u8f38\u51fa<\/th><\/tr><\/thead>
\u7b2c\u4e00\u884c\u6709 4 \u500b\u6b63\u6574 N\u3001M\u3001L\u3001Q (N\u3001L\u3001Q <= 10000\uff0cM <= 100000)\uff0cN \u70ba\u5ee0\u5546\u6578\u91cf (\u7de8\u865f\u70ba 1\uff5eN)\u3002
\u63a5\u4e0b\u4f86 M \u884c\u6bcf\u884c\u6709\u5169\u500b\u6578\u5b57 a \u548c b\uff0c\u8868\u793a a \u5ee0\u5546\u4f9b\u61c9\u539f\u6599\u7d66 b \u5ee0\u5546\u3002
\u518d\u63a5\u4e0b\u4f86 L \u884c\uff0c\u6bcf\u884c\u6709\u4e00\u500b\u6578\u5b57 x\uff0c\u8868\u793a x \u5ee0\u5546\u662f\u6709\u554f\u984c\u7684\u3002
\u518d\u63a5\u4e0b\u4f86 Q \u884c\u6bcf\u884c\u6709\u4e00\u500b\u6578\u5b57 y\uff0c\u8a62\u554f y \u5ee0\u5546\u662f\u5426\u6709\u554f\u984c\u3002<\/td>		\u5c0d\u6bcf\u4e00\u7b46\u8a62\u554f\uff0c\u82e5\u6c92\u554f\u984c\u5247\u8f38\u51fa\u300cYA~~\u300d\uff0c\u5426\u5247\u8f38\u51fa\u300cTUIHUOOOOOO\u300d\uff0c\u4e00\u7b46\u8a62\u554f\u4e00\u884c\u3002<\/td><\/tr>
5 3 1 2
1 2
1 3
3 4
3
2
4<\/td>		YA~~
TUIHUOOOOOO<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

\u89e3\u984c\u601d\u8def<\/h2>\n\n\n\n

\u7d00\u9304\u6bcf\u4e00\u500b\u5ee0\u5546\u7684\u4e0b\u6e38\u5ee0\u5546\u6709\u8ab0\uff0c\u5728\u6536 L \u500b\u6709\u554f\u984c\u7684\u6642\u5019\u5c07\u6536\u5230\u7684\u5ee0\u5546\u9084\u6709\u4ed6\u7684\u6240\u6709\u4e0b\u6e38\u5ee0\u5546\u505a\u7d00\u9304\uff0c\u53ef\u4ee5\u4f7f\u7528 BFS \u7684\u65b9\u5f0f\u4f86\u5c07\u6240\u6709\u4e0b\u6e38\u5ee0\u5546\u8dd1\u4e00\u904d\u3002\u5728\u9032\u884c Q \u6b21\u8a62\u554f\u6642\u53ea\u9700\u8981\u770b\u8a62\u554f\u7684\u5ee0\u5546\u6709\u6c92\u6709\u88ab\u7d00\u9304\u5373\u53ef\u3002<\/p>\n\n\n\n

\u7bc4\u4f8b\u7a0b\u5f0f\u78bc\uff0dZeroJudge B298: \u8001\u95c6\u963f\u6211\u8981\u9000\u8ca8<\/a><\/h3>\n\n\n\n
#include <iostream>\n#include <vector>\n#include <map>\nusing namespace std;\n\nint problem[10001] = {}, walk[10001] = {};\n\nvector<int> MAP[10001] = {};\n\nvoid BFS(const vector<int>start) {\n    if (start.size() == 0) return;\n    vector<int>newStart;\n    map<int, int>push;\n    for (int i = 0; i<start.size(); i++) {\n        const int num = start[i];\n        walk[num]++;\n        const vector<int> v = MAP[num];\n        for (int j = 0; j<v.size(); j++) {\n            const int vv = v[j];\n            problem[vv]++;\n            if (walk[vv] == 0 && push[vv] == 0) {\n                push[vv]++;\n                newStart.push_back(vv);\n            }\n        }\n    }\n    BFS(newStart);\n}\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    int N, M, L, Q;\n    cin >> N >> M >> L >> Q;\n    for (int i = 1; i<=N; i++) {\n        problem[i] = 0;\n        vector<int> tmp;\n        MAP[i] = tmp;\n        walk[i] = 0;\n    }\n    for (int i = 0; i<M; i++) {\n        int a, b;\n        cin >> a >> b;\n        MAP[a].push_back(b);\n    }\n    for (int i = 0; i<L; i++) {\n        int x;\n        cin >> x;\n        problem[x]++;\n        vector<int>tmp;\n        tmp.push_back(x);\n        BFS(tmp);\n    }\n    for (int i = 0; i<Q; i++) {\n        int y;\n        cin >> y;\n        if (problem[y] == 0) cout << "YA~~\\n";\n        else cout << "TUIHUOOOOOO\\n";\n    }\n}\n\n\/\/ZeroJudge B298\n\/\/Dr. SeanXD<\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"
\u53f0\u7063\u7684\u6771\u897f\u771f\u7684\u8d85\u597d\u5403\uff0c\u4f46\u662f\u6700\u8fd1\u7206\u767c\u4e86\u98df\u5b89\u554f\u984c\uff0c\u5bb3\u5f97\u81fa\u7063\u4eba\u5fc3\u60f6\u60f6\uff0c\u5f15\u767c\u9000\u8ca8\u6f6e\u3002\u4f60\u5bb6\u88e1\u525b\u597d\u8cb7\u4e86\u4e00\u5927\u5806\u6708\u9905\uff0c\u4f60\u60f3\u8981\u62ff […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","footnotes":""},"categories":[6],"tags":[30,14,20,8,9],"class_list":["post-1115","post","type-post","status-publish","format-standard","hentry","category-6","tag-bfs","tag-map","tag-20","tag-8","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1115","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/comments?post=1115"}],"version-history":[{"count":1,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1115\/revisions"}],"predecessor-version":[{"id":1116,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1115\/revisions\/1116"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/media?parent=1115"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/categories?post=1115"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/tags?post=1115"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}