結果
問題 | No.1605 Matrix Shape |
ユーザー | nebukuro09 |
提出日時 | 2021-07-16 22:04:38 |
言語 | D (dmd 2.105.2) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,013 bytes |
コンパイル時間 | 1,273 ms |
コンパイル使用メモリ | 106,596 KB |
実行使用メモリ | 43,512 KB |
最終ジャッジ日時 | 2023-09-04 13:14:26 |
合計ジャッジ時間 | 8,407 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
4,384 KB |
testcase_01 | AC | 3 ms
4,804 KB |
testcase_02 | AC | 3 ms
5,392 KB |
testcase_03 | AC | 3 ms
4,384 KB |
testcase_04 | AC | 3 ms
4,868 KB |
testcase_05 | AC | 3 ms
5,664 KB |
testcase_06 | WA | - |
testcase_07 | AC | 2 ms
5,132 KB |
testcase_08 | AC | 3 ms
5,300 KB |
testcase_09 | AC | 2 ms
4,856 KB |
testcase_10 | AC | 2 ms
5,040 KB |
testcase_11 | AC | 3 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 3 ms
4,384 KB |
testcase_14 | AC | 3 ms
4,384 KB |
testcase_15 | AC | 3 ms
5,364 KB |
testcase_16 | AC | 3 ms
4,380 KB |
testcase_17 | AC | 3 ms
5,064 KB |
testcase_18 | AC | 2 ms
4,380 KB |
testcase_19 | AC | 364 ms
43,512 KB |
testcase_20 | WA | - |
testcase_21 | AC | 178 ms
15,792 KB |
testcase_22 | AC | 359 ms
41,056 KB |
testcase_23 | AC | 374 ms
43,116 KB |
testcase_24 | AC | 187 ms
17,364 KB |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | AC | 169 ms
17,548 KB |
testcase_28 | AC | 202 ms
16,480 KB |
testcase_29 | AC | 167 ms
16,040 KB |
testcase_30 | WA | - |
testcase_31 | AC | 179 ms
15,948 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 203 ms
17,828 KB |
testcase_35 | AC | 147 ms
15,084 KB |
testcase_36 | AC | 88 ms
14,056 KB |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; void main() { auto N = readln.chomp.to!int; auto A = iota(N).map!(_ => readln.split.map!(to!int).array).array; auto X = new int[](2*10^^5+10); auto Y = new int[](2*10^^5+10); foreach (a; A) X[a[0]]++; foreach (a; A) Y[a[1]]++; int indeg = 0; int outdeg = 0; foreach (i; 0..2*10^^5+10) { auto diff = X[i] - Y[i]; if (abs(diff) >= 2) { writeln(0); return; } if (diff == 1) { indeg += 1; } else if (diff == -1) { outdeg += 1; } } if (indeg == 1 && outdeg == 1) { writeln(1); return; } if (indeg == 0 && outdeg == 0) { auto uf = new UnionFind(N); int[int] dict_in; int[int] dict_out; foreach (i, a; A) { if (a[0] in dict_out) { uf.unite(i.to!int, dict_out[a[0]]); } if (a[1] in dict_in) { uf.unite(i.to!int, dict_in[a[1]]); } dict_in[a[0]] = i.to!int; dict_out[a[1]] = i.to!int; } if (uf.table[uf.find(0)] == -N) { writeln(dict_in.keys.length); return; } writeln(0); return; } writeln(0); return; } class UnionFind { import std.algorithm : swap; int n; int[] table; this(int n) { this.n = n; table = new int[](n); table[] = -1; } int find(int x) { return table[x] < 0 ? x : (table[x] = find(table[x])); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (table[x] > table[y]) swap(x, y); table[x] += table[y]; table[y] = x; } bool same(int x, int y) { return find(x) == find(y); } }