{"id":1147,"date":"2024-08-27T09:00:00","date_gmt":"2024-08-27T01:00:00","guid":{"rendered":"https:\/\/seanxd.com\/?p=1147"},"modified":"2024-07-31T11:23:37","modified_gmt":"2024-07-31T03:23:37","slug":"zerojudge-g598","status":"publish","type":"post","link":"https:\/\/seanxd.com\/en\/zerojudge-g598\/","title":{"rendered":"ZeroJudge G598: Investigation Pair"},"content":{"rendered":"\n\n\n<p>\u60c5\u5831\u8abf\u67e5\u5c40\u5167\u6709&nbsp;N&nbsp;\u500b\u5de5\u4f5c\u4eba\u54e1\uff0c\u8abf\u67e5\u5c40\u8ca0\u8cac\u4eba\u5c07\u9019\u4e9b\u4eba\u79d8\u5bc6\u5206\u6210\u5169\u7d44&nbsp;A&nbsp;\u548c&nbsp;B&nbsp;\u4e26\u4e0d\u8b93\u5176\u4ed6\u4eba\u77e5\u9053\uff0c\u4e26\u5c07\u5408\u4f5c\u540d\u55ae\u5206\u914d\u7d66\u7d44\u9577\uff0c\u5408\u4f5c\u540d\u55ae\u662f\u7531\u5f88\u591a\u500b pair \u7d44\u6210\uff0c\u6bcf\u500b pair&nbsp;(x, y)&nbsp;\u4ee3\u8868&nbsp;x&nbsp;\u548c&nbsp;y&nbsp;\u9700\u8981\u5408\u4f5c\u5b8c\u6210\u4efb\u52d9\uff0c\u4e26\u4e14\u4fdd\u8b49&nbsp;x&nbsp;\u548c&nbsp;y&nbsp;\u4e0d\u6703\u540c\u6642\u5728&nbsp;A&nbsp;\u7d44\u6216\u662f\u540c\u6642\u5728&nbsp;B&nbsp;\u7d44\u3002<\/p>\n\n\n\n<p>\u7d44\u9577\u4e0d\u5c0f\u5fc3\u5c07\u9019\u500b\u5408\u4f5c\u540d\u55ae\u5206\u914d\u907a\u5931\uff0c\u50c5\u5269\u4e0b\u5176\u4e2d&nbsp;M&nbsp;\u500b pair\uff0c\u70ba\u4e86\u8981\u5fa9\u539f\u9019\u4e9b\u5931\u53bb\u7684\u8cc7\u6599\uff0c\u7d44\u9577\u6d3e\u51fa\u4e86\u53e6\u5916&nbsp;P&nbsp;\u500b\u8abf\u67e5\u54e1\u7de8\u865f&nbsp;1&nbsp;\u5230&nbsp;P&nbsp;\u53bb\u8abf\u67e5\u9019\u500b\u5408\u4f5c\u95dc\u4fc2\uff0c\u6bcf\u4e00\u500b\u8abf\u67e5\u54e1\u90fd\u6703\u56de\u50b3\u6070\u597d&nbsp;K&nbsp;\u500b pair \u7684\u8cc7\u6599\u56de\u4f86\u3002<\/p>\n\n\n\n<p>\u6709\u4e9b\u8abf\u67e5\u54e1\u56de\u50b3\u7684\u8cc7\u6599\u548c\u7d44\u9577\u624b\u4e0a\u7684\u8cc7\u6599\u6703\u7522\u751f\u77db\u76fe (\u610f\u5373\u52a0\u4e0a\u9019&nbsp;K&nbsp;\u500b pair \u548c\u7d44\u9577\u624b\u4e0a\u5b58\u7559\u7684&nbsp;M&nbsp;\u500b pair \u6703\u4f7f\u5f97\u9019\u4e9b\u4eba\u662f\u88ab\u5206\u6210&nbsp;A\u3001B&nbsp;\u5169\u7d44\u9019\u4ef6\u4e8b\u7522\u751f\u77db\u76fe)\uff0c\u8acb\u5c07\u56de\u50b3\u932f\u8aa4\u7d50\u679c\u7684\u8abf\u67e5\u54e1\u7de8\u865f\u7531\u5c0f\u5230\u5927\u8f38\u51fa\u51fa\u4f86\uff0c\u4fdd\u8b49\u81f3\u5c11\u4e00\u500b\u4e14\u6700\u591a\u4e09\u500b\u3002<\/p>\n\n\n\n<p>\u53e6\u5916\u4fdd\u8b49\u82e5\u8abf\u67e5\u54e1\u7684 K \u500b pair \u7684\u7d50\u679c\u548c\u7d44\u9577\u5b58\u7559\u7684 M \u500b pair \u4e0d\u6703\u7522\u751f\u77db\u76fe\uff0c\u5247\u4fdd\u8b49\u8abf\u67e5\u54e1\u7684\u8cc7\u6599\u4e00\u5b9a\u548c\u539f\u672c&nbsp;A\u3001B&nbsp;\u5206\u7d44\u543b\u5408\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u7bc4\u4f8b\u6e2c\u8cc7<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>\u7bc4\u4f8b\u8f38\u5165<\/th><th>\u7bc4\u4f8b\u8f38\u51fa<\/th><\/tr><\/thead><tbody><tr><td>\u7b2c\u4e00\u884c\u5148\u8f38\u51fa\u5169\u500b\u6b63\u6574\u6578\u00a0N \u548c M\u3002<br>\u7b2c\u4e8c\u884c\u4f86\u6709\u00a02\uff0aM \u500b\u975e\u8ca0\u6574\u6578\u5169\u5169\u5f62\u6210\u4e00\u500b\u6578\u5c0d\uff0c\u8868\u793a\u76ee\u524d\u9084\u7559\u5b58\u7684\u00a0M \u500b pair\u3002<br>\u7b2c\u4e09\u884c\u6709\u5169\u500b\u6b63\u6574\u6578\u00a0P\u00a0\u548c K\uff0c\u4e26\u4e14\u63a5\u4e0b\u4f86\u7684\u884c P \u6bcf\u884c\u6709 2\uff0aK \u500b\u975e\u8ca0\u6574\u6578, \u5169\u5169\u5f62\u6210\u4e00\u5c0d\u4ee3\u8868\u67d0\u500b\u8abf\u67e5\u54e1\u627e\u5230\u7684 K \u500b pair\u3002<\/td><td>\u7531\u5c0f\u5230\u5927\u8f38\u51fa\u6703\u5f62\u6210\u77db\u76fe\u7684\u8abf\u67e5\u54e1\u7de8\u865f\uff0c\u6bcf\u500b\u7de8\u865f\u5404\u81ea\u7368\u7acb\u4e00\u884c\u3002<\/td><\/tr><tr><td>7 5<br>0 1 0 2 1 3 2 3 4 5<br>2 3<br>0 6 2 4 3 6<br>0 6 0 3 3 5<\/td><td>2<\/td><\/tr><tr><td>5 2<br>0 3 2 3<br>3 2<br>0 2 2 4<br>0 1 1 2<br>3 4 2 4<\/td><td>1<br>3<\/td><\/tr><\/tbody><\/table><figcaption class=\"wp-element-caption\">ZeroJudge G598 \u7bc4\u4f8b\u6e2c\u8cc7<\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">\u89e3\u984c\u601d\u8def<\/h2>\n\n\n\n<p>\u4f7f\u7528\u4e26\u67e5\u96c6\u7684\u65b9\u5f0f\u4f86\u505a\u8cc7\u6599\u7684\u5b58\u5132\uff0c\u7576\u5728\u6536 2\uff0aM \u500b pair \u7684\u6642\u5019\uff0c\u8dd1\u4e00\u500b\u51fd\u5f0f\u4f86\u66f4\u65b0\u5169\u500b\u5168\u57df\u9663\u5217\u4e2d\u7684\u8cc7\u6599\uff0c\u5169\u500b\u9663\u5217\u5206\u5225\u70ba friends \u548c enemies\uff0c\u4ee3\u8868\u6bcf\u4e00\u500b\u4eba\u4ed6\u7684\u968a\u53cb\u548c\u53e6\u5916\u4e00\u7d44\u7684\u4eba\u3002\u5728\u7a0b\u5f0f\u4e00\u958b\u59cb\u6642\u53ef\u4ee5\u5c07\u5169\u500b\u9663\u5217\u5f9e 0 \u5230 N-1 \u5206\u5225\u9810\u8a2d\u70ba -1\u3002\u5982\u679c\u9032\u51fd\u5f0f\u6642\u5169\u500b\u4eba\u7684 friends \u9663\u5217\u8cc7\u6599\u90fd\u662f -1\uff0c\u4ee3\u8868\u5169\u500b\u4eba\u90fd\u6c92\u6709\u505a\u904e\u5224\u65b7\uff0c\u6240\u4ee5\u5c31\u5c07 friends \u8a2d\u70ba\u81ea\u5df1\u3001enemies \u8a2d\u70ba\u53e6\u5916\u4e00\u500b\u4eba\u3002\u5982\u679c\u5169\u500b\u4eba\u7684 friends \u9663\u5217\u8cc7\u6599\u90fd != -1\uff0c\u4ee3\u8868\u5169\u500b\u4eba\u90fd\u6709\u5224\u65b7\u904e\uff0c\u9019\u908a\u8981\u5c07\u5169\u500b\u4eba\u6240\u6709\u7684\u670b\u53cb\u548c\u6575\u4eba\u90fd\u5206\u5225\u8a2d\u7f6e\u70ba\u65b0\u7684\u670b\u53cb\u548c\u6575\u4eba\uff0c\u4e0b\u9762\u7684\u7a0b\u5f0f\u78bc\u662f\u4f7f\u7528\u51fd\u5f0f\u7684\u65b9\u5f0f\u53bb\u505a\u905e\u8ff4\u5c07\u6bcf\u4e00\u500b\u4eba\u7684\u670b\u53cb\u3001\u6575\u4eba\u8a2d\u5b9a\u70ba\u65b0\u7684\u4eba\u3002\u5982\u679c\u662f\u5176\u4e2d\u4e00\u500b\u4eba\u5df2\u7d93\u6709\u8cc7\u6599\u53e6\u5916\u4e00\u500b\u4eba\u662f -1\uff0c\u5247\u662f\u5c07\u6c92\u6709\u8cc7\u6599\u7684\u4eba\u7684 friends \u8a2d\u5b9a\u70ba\u53e6\u5916\u4e00\u4eba\u7684\u6575\u4eba\u7684\u670b\u53cb\u6839\u7bc0\u9ede\u3001enemies \u8a2d\u5b9a\u70ba\u53e6\u5916\u4e00\u500b\u4eba\u7684\u670b\u53cb\u6839\u7bc0\u9ede\u3002<\/p>\n\n\n\n<p>\u5728\u5224\u65b7\u65b0\u7684 pair \u662f\u5426\u6b63\u78ba\u6642\u4e5f\u9700\u8981\u505a\u8cc7\u6599\u7684\u5224\u65b7\uff0c\u6240\u4ee5\u53ef\u4ee5\u91cd\u65b0\u5ba3\u544a\u4e00\u500b newFriend \u548c newEnemy\uff0c\u4e26\u5c07 friends \u548c enemies \u7684\u8cc7\u6599\u79fb\u904e\u53bb\uff0c\u6536\u5230\u65b0\u7684\u8981\u5224\u65b7\u7684 pair \u6642\uff0c\u8981\u505a\u7684\u4e8b\u60c5\u5176\u5be6\u548c\u4e0a\u9762\u7684\u5dee\u4e0d\u591a\uff0c\u53ea\u662f\u7576\u5169\u500b\u4eba\u7684 newFriend \u548c newEnemy \u90fd\u6709\u505a\u904e\u5224\u65b7\u6642\u5c31\u4e0d\u9700\u8981\u505a\u5224\u65b7\uff0c\u8dd1\u5b8c\u51fd\u5f0f\u4e4b\u5f8c\u5c31\u662f\u5224\u65b7 newFriend[a] \u662f\u5426 == newFriend[b]\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u7bc4\u4f8b\u7a0b\u5f0f\u78bc\uff0d<a href=\"https:\/\/zerojudge.tw\/ShowProblem?problemid=g598\" target=\"_blank\" rel=\"noreferrer noopener\">ZeroJudge G598: \u771f\u5047\u5b50\u5716<\/a><\/h3>\n\n\n\n<div class=\"hcb_wrap\"><pre class=\"prism line-numbers lang-cpp\" data-lang=\"C++\"><code>#include &lt;iostream&gt;\nusing namespace std;\n\nint friends[100000] = {}, enemies[100000] = {};\nint newFriend[100000] = {}, newEnemy[100000] = {};\n\nint findEnd(const int N) {\n    if (N == -1 || friends[N] == -1) return -1;\n    if (friends[N] == N) return N;\n    return findEnd(friends[N]);\n}\n\nint newFind(const int N) {\n    if (N == -1 || newFriend[N] == -1) return -1;\n    if (newFriend[N] == N) return N;\n    return newFind(newFriend[N]);\n}\n\nvoid meet(const int target, const int value) {\n    if (friends[target] == target) {\n        friends[target] = value;\n        return;\n    }\n    meet(friends[target], value);\n    friends[target] = value;\n}\n\nvoid kill(const int target, const int value) {\n    if (enemies[target] == target) {\n        enemies[target] = value;\n        return;\n    }\n    meet(enemies[target], value);\n    enemies[target] = value;\n}\n\nvoid people(const int a, const int b) {\n    if (friends[a] == -1 && friends[b] == -1) {\n        friends[a] = a;\n        friends[b] = b;\n        enemies[a] = b;\n        enemies[b] = a;\n    }\n    else if (friends[a] != -1 && friends[b] != -1) {\n        meet(a, findEnd(enemies[b]));\n        meet(b, findEnd(enemies[a]));\n        kill(a, findEnd(b));\n        kill(b, findEnd(a));\n    }\n    else {\n        if (friends[a] == -1) {\n            friends[a] = findEnd(enemies[b]);\n            enemies[a] = findEnd(b);\n        }\n        else {\n            friends[b] = findEnd(enemies[a]);\n            enemies[b] = findEnd(a);\n        }\n    }\n}\n\nvoid check(const int a, const int b) {\n    if (newFriend[a] == -1 && newFriend[b] == -1) {\n        newFriend[a] = a;\n        newFriend[b] = b;\n        newEnemy[a] = b;\n        newEnemy[b] = a;\n        return;\n    }\n    if (newFriend[a] != -1 && newFriend[b] != -1) return;\n    if (newFriend[a] == -1) {\n        newFriend[a] = newFind(newEnemy[b]);\n        newEnemy[a] = newFind(b);\n        return;\n    }\n    newFriend[b] = newFind(newEnemy[a]);\n    newEnemy[b] = newFind(a);\n}\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    int N, M;\n    cin &gt;&gt; N &gt;&gt; M;\n    for (int i = 0; i&lt;N; i++) {\n        friends[i] = -1;\n        enemies[i] = -1;\n    }\n    for (int i = 0; i&lt;M; i++) {\n        int a, b;\n        cin &gt;&gt; a &gt;&gt; b;\n        people(a, b);\n    }\n    int P, K;\n    cin &gt;&gt; P &gt;&gt; K;\n    for (int i = 1; i&lt;=P; i++) {\n        bool window = false;\n        for (int j = 0; j&lt;N; j++) {\n            newFriend[j] = -1;\n            newEnemy[j] = -1;\n            if (friends[j] != -1) newFriend[j] = friends[j];\n            if (enemies[j] != -1) newEnemy[j] = enemies[j];\n        }\n        for (int j = 0; j&lt;K; j++) {\n            int a, b;\n            cin &gt;&gt; a &gt;&gt; b;\n            if (window) continue;\n            check(a, b);\n            if (newFind(a) == newFind(b)) {\n                window = true;\n            }\n        }\n        if (window) cout &lt;&lt; i &lt;&lt; &quot;\\n&quot;;\n    }\n}\n\n\/\/ZeroJudge G598\n\/\/Dr. SeanXD<\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u60c5\u5831\u8abf\u67e5\u5c40\u5167\u6709&nbsp;N&nbsp;\u500b\u5de5\u4f5c\u4eba\u54e1\uff0c\u8abf\u67e5\u5c40\u8ca0\u8cac\u4eba\u5c07\u9019\u4e9b\u4eba\u79d8\u5bc6\u5206\u6210\u5169\u7d44&nbsp;A&nbsp; [&hellip;]<\/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":[25],"tags":[20,40,8,34,9],"class_list":["post-1147","post","type-post","status-publish","format-standard","hentry","category-ioi-apcs","tag-20","tag-40","tag-8","tag-34","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1147","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=1147"}],"version-history":[{"count":3,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1147\/revisions"}],"predecessor-version":[{"id":1150,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1147\/revisions\/1150"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/media?parent=1147"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/categories?post=1147"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/tags?post=1147"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}