提出 #41975701

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <unordered_set>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

int main (void) {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int> > original_edges(m);
    for (int i=0; i<m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        original_edges[i] = make_pair(u, v);
    }
    int k;
    cin >> k;
    vector<pair<int, int> > taboos(k);
    for (int i=0; i<k; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        taboos[i] = make_pair(x, y);
    }
    int q;
    cin >> q;
    vector<pair<int, int> > additional_edges(q);
    for (int i=0; i<q; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        additional_edges[i] = make_pair(u, v);
    }
    dsu d(n);
    for (const auto& edge : original_edges) {
        d.merge(edge.first, edge.second);
    }
    bool init_is_good = true;
    set<pair<int, int> > s;
    for (const auto& taboo : taboos) {
        int x = taboo.first;
        int y = taboo.second;
        if (d.same(x, y)) {
            init_is_good = false;
            break;
        }
        pair<int, int> p = make_pair(min(d.leader(x), d.leader(y)), max(d.leader(x), d.leader(y)));
        s.insert(p);
    }
    if (!init_is_good) {
        for (int i=0; i<q; i++) {
            cout << "No" << endl;
        }
    }
    for (const auto& edge : additional_edges) {
        int u = edge.first;
        int v = edge.second;
        pair<int, int> p = make_pair(min(d.leader(u), d.leader(v)), max(d.leader(u), d.leader(v)));
        if (s.find(p) == s.end()) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

提出情報

提出日時
問題 E - Good Graph
ユーザ ReiAkiduki
言語 C++ (GCC 9.2.1)
得点 475
コード長 1879 Byte
結果 AC
実行時間 687 ms
メモリ 18080 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 475 / 475
結果
AC × 1
AC × 62
セット名 テストケース
Sample example0.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, example0.txt
ケース名 結果 実行時間 メモリ
000.txt AC 590 ms 16396 KiB
001.txt AC 518 ms 8844 KiB
002.txt AC 666 ms 18080 KiB
003.txt AC 316 ms 4884 KiB
004.txt AC 520 ms 16420 KiB
005.txt AC 530 ms 11480 KiB
006.txt AC 477 ms 7640 KiB
007.txt AC 453 ms 7340 KiB
008.txt AC 547 ms 9312 KiB
009.txt AC 485 ms 10368 KiB
010.txt AC 442 ms 7084 KiB
011.txt AC 470 ms 7608 KiB
012.txt AC 513 ms 8720 KiB
013.txt AC 436 ms 7132 KiB
014.txt AC 506 ms 8520 KiB
015.txt AC 518 ms 8760 KiB
016.txt AC 443 ms 7132 KiB
017.txt AC 450 ms 7024 KiB
018.txt AC 528 ms 8636 KiB
019.txt AC 449 ms 7156 KiB
020.txt AC 515 ms 8576 KiB
021.txt AC 524 ms 8844 KiB
022.txt AC 447 ms 7112 KiB
023.txt AC 499 ms 7940 KiB
024.txt AC 530 ms 8716 KiB
025.txt AC 451 ms 7176 KiB
026.txt AC 467 ms 7180 KiB
027.txt AC 536 ms 8780 KiB
028.txt AC 443 ms 7088 KiB
029.txt AC 546 ms 8844 KiB
030.txt AC 560 ms 9048 KiB
031.txt AC 439 ms 7088 KiB
032.txt AC 529 ms 8868 KiB
033.txt AC 595 ms 10080 KiB
034.txt AC 451 ms 7200 KiB
035.txt AC 490 ms 8340 KiB
036.txt AC 618 ms 11624 KiB
037.txt AC 444 ms 7080 KiB
038.txt AC 578 ms 12476 KiB
039.txt AC 639 ms 15124 KiB
040.txt AC 454 ms 7152 KiB
041.txt AC 628 ms 15124 KiB
042.txt AC 687 ms 17408 KiB
043.txt AC 446 ms 7256 KiB
044.txt AC 591 ms 13648 KiB
045.txt AC 651 ms 17720 KiB
046.txt AC 456 ms 7088 KiB
047.txt AC 624 ms 13620 KiB
048.txt AC 675 ms 18004 KiB
049.txt AC 452 ms 7112 KiB
050.txt AC 522 ms 9452 KiB
051.txt AC 651 ms 17912 KiB
052.txt AC 444 ms 7160 KiB
053.txt AC 461 ms 7084 KiB
054.txt AC 661 ms 18080 KiB
055.txt AC 455 ms 7192 KiB
056.txt AC 638 ms 16640 KiB
057.txt AC 683 ms 17956 KiB
058.txt AC 454 ms 7168 KiB
059.txt AC 590 ms 13444 KiB
060.txt AC 660 ms 18000 KiB
example0.txt AC 4 ms 3564 KiB