Contest Duration: - (local time) (100 minutes) Back to Home

Submission #17611116

Source Code Expand

Copy
```import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit
def find_root(uf, x):
root = uf[0]
while root[x] != x:
root[x] = root[root[x]]
x = root[x]
return x

@njit
def merge(uf, x, y):
root, size = uf
x, y = find_root(uf, x), find_root(uf, y)
if x == y:
return False
if size[x] < size[y]:
x, y = y, x
size[x] += size[y]
root[y] = root[x]
return True

@njit((i8[:], i8[:], i8[:, :]), cache=True)
def main(A, B, G):
N = len(A)
root = np.arange(N + 1)
size = np.ones_like(root)
uf = (root, size)

M = len(G)
for e in range(M):
c, d = G[e]
merge(uf, c, d)

comp_sum = np.zeros(N + 1, np.int64)
for i in range(1, N + 1):
r = find_root(uf, i)
comp_sum[r] += A[i - 1] - B[i - 1]
return np.all(comp_sum == 0)

print('Yes' if main(A, B, G) else 'No')```

Submission Info

Submission Time 2020-10-24 21:05:34+0900 B - Values maspy Python (3.8.2) 400 1388 Byte AC 521 ms 116932 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
 AC × 4
 AC × 44
Set Name Test Cases
Sample 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03
All 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 01_small_0, 01_small_1, 01_small_2, 01_small_3, 01_small_4, 01_small_5, 01_small_6, 01_small_7, 01_small_8, 01_small_9, 02_large_0, 02_large_1, 02_largecon_0, 02_largecon_1, 02_largecon_2, 02_largecon_3, 02_largecon_4, 02_largecon_5, 02_toolarge_0, 02_toolarge_1, 02_toolarge_2, 02_toolarge_3, 03_few_e_0, 03_few_e_1, 03_few_e_2, 03_few_e_3, 03_few_e_4, 03_few_e_5, 03_is_tree_0, 03_is_tree_1, 03_is_tree_2, 03_is_tree_3, 04_kill_overflow_0, 04_kill_overflow_1, 04_kill_overflow_2, 04_kill_overflow_3, 04_sumequal_0, 04_sumequal_1, 04_sumequal_2, 04_sumequal_3
Case Name Status Exec Time Memory
00_sample_00 AC 484 ms 106044 KB
00_sample_01 AC 460 ms 106704 KB
00_sample_02 AC 461 ms 106016 KB
00_sample_03 AC 466 ms 105568 KB
01_small_0 AC 463 ms 105996 KB
01_small_1 AC 462 ms 105972 KB
01_small_2 AC 472 ms 106708 KB
01_small_3 AC 453 ms 106096 KB
01_small_4 AC 460 ms 106044 KB
01_small_5 AC 455 ms 106000 KB
01_small_6 AC 463 ms 106592 KB
01_small_7 AC 458 ms 105984 KB
01_small_8 AC 464 ms 106032 KB
01_small_9 AC 460 ms 106232 KB
02_large_0 AC 497 ms 111944 KB
02_large_1 AC 474 ms 109100 KB
02_largecon_0 AC 512 ms 114540 KB
02_largecon_1 AC 521 ms 115156 KB
02_largecon_2 AC 511 ms 114228 KB
02_largecon_3 AC 490 ms 113820 KB
02_largecon_4 AC 508 ms 116840 KB
02_largecon_5 AC 515 ms 114408 KB
02_toolarge_0 AC 513 ms 116932 KB
02_toolarge_1 AC 521 ms 116716 KB
02_toolarge_2 AC 509 ms 116000 KB
02_toolarge_3 AC 520 ms 116264 KB
03_few_e_0 AC 476 ms 110740 KB
03_few_e_1 AC 480 ms 112388 KB
03_few_e_2 AC 480 ms 110924 KB
03_few_e_3 AC 494 ms 112652 KB
03_few_e_4 AC 490 ms 113036 KB
03_few_e_5 AC 483 ms 111596 KB
03_is_tree_0 AC 499 ms 113656 KB
03_is_tree_1 AC 495 ms 111824 KB
03_is_tree_2 AC 493 ms 111892 KB
03_is_tree_3 AC 494 ms 111620 KB
04_kill_overflow_0 AC 519 ms 116364 KB
04_kill_overflow_1 AC 506 ms 114848 KB
04_kill_overflow_2 AC 513 ms 114888 KB
04_kill_overflow_3 AC 509 ms 113424 KB
04_sumequal_0 AC 491 ms 111728 KB
04_sumequal_1 AC 483 ms 108756 KB
04_sumequal_2 AC 468 ms 107580 KB
04_sumequal_3 AC 478 ms 109740 KB