#588504 (C++14) No.1326 ふたりのDominator

• 問題: No.1326 ふたりのDominator
• ユーザー: QCFium
• 提出日時: 2020-12-03 01:33:39
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 1,989 bytes
• コンパイル時間: 1,672 ms
• コンパイル使用メモリ: 177,220 KB
• 実行使用メモリ: 8,320 KB
• 最終ジャッジ日時: 2024-09-23 02:53:46
• 合計ジャッジ時間: 3,229 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
sample	WA * 1
other	WA * 24

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
struct UnionFind {
    std::vector<int> data;
    UnionFind (int size) : data(size, -1) {}
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) std::swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
    int size(int x) { return -data[root(x)]; }
    bool connected() { return size(0) == (int) data.size(); }
};
/* strict input checker */
template<class Int = int> int read_int() {
    static_assert(std::numeric_limits<Int>::is_specialized);
    int c = getchar(), s = 0;
    Int res = 0;
    if (c == '-') s = 1, c = getchar();
    assert('0' <= c && c <= '9');
    if (s) assert(c != '0');
    res = c - '0';
    while (1) {
        c = getchar();
        if (c < '0' || c > '9') break;
        assert(res < std::numeric_limits<Int>::max() / 10); // avoid overflow
        assert(res); // no leading-zero
        res = res * 10 + c - '0';
    }
    ungetc(c, stdin);
    return s ? -res : res;
}
void read_linebreak() {
    int c = getchar();
    if (c == '\r') c = getchar();
    assert(c == '\n');
}
int main() {
    int n = read_int();
    assert(getchar() == ' ');
    int m = read_int();
    read_linebreak();
    
    assert(3 <= n && n <= 50000);
    assert(n - 1 <= m && m <= 100000);
    
    UnionFind uni(n);
    std::set<std::pair<int, int> > used;
    for (int i = 0; i < m; i++) {
        int a = read_int();
        assert(getchar() == ' ');
        int b = read_int();
        read_linebreak();
        
        assert(1 <= a && a <= n);
        assert(1 <= b && b <= n);
        assert(a != b);
        assert(used.insert(std::minmax(a, b)).second);
        uni.unite(a - 1, b - 1);
    }
    assert(uni.connected());
    
    int q = read_int();
    read_linebreak();
    
    assert(1 <= q && q <= 100000);
    
    for (int i = 0; i < q; i++) {
        int a = read_int();
        assert(getchar() == ' ');
        int b = read_int();
        read_linebreak();
        
        assert(1 <= a && a <= n);
        assert(1 <= b && b <= n);
    }
    
    assert(getchar() == EOF);
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX