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

Submission #4469736

Source Code Expand

Copy
```N,M = map(int,input().split())
L = []
for i in range(M):
L.append(list(map(int,input().split())))
L.reverse()
par = []
rank = [0]*N
size = [1]*N
for i in range(N):
par.append(i)
def find(x,par):
if x == par[x]:
return x
else:
return find(par[x],par)
def unite(x,y,par,rank,size):
x = find(x,par)
y = find(y,par)
if x != y:
if rank[x] < rank[y]:
par[x] = y
size[y] += size[x]
else:
par[y] = x
size[x] += size[y]
if rank[x] == rank[y]:
rank[x] += 1
def same(x,y,par):
return find(x,par) == find(y,par)

res = []
for i in range(M):
A = find(L[i][0]-1,par)
B = find(L[i][1]-1,par)
if A == B:
res.append(0)
else:
res.append(size[A]*size[B])
unite(A,B,par,rank,size)
ans = 0
for i in range(M):
ans += res[M-i-1]
print(ans)```

#### Submission Info

Submission Time 2019-03-04 21:20:48+0900 D - Decayed Bridges Syuko4omi Python3 (3.4.3) 400 869 Byte AC 749 ms 35420 KB

#### Test Cases

Set Name Score / Max Score Test Cases
All 400 / 400 sample_01, sample_02, sample_03, testcase_01, testcase_02, testcase_03, testcase_04, testcase_05, testcase_06, testcase_07, testcase_08, testcase_09, testcase_10, testcase_11, testcase_12, testcase_13, testcase_14, testcase_15, testcase_16, testcase_17, testcase_18, testcase_19, testcase_20, testcase_21, testcase_22, testcase_23
Sample 0 / 0 sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
sample_01 20 ms 3064 KB
sample_02 19 ms 3064 KB
sample_03 20 ms 3064 KB
testcase_01 20 ms 3064 KB
testcase_02 542 ms 26580 KB
testcase_03 672 ms 32596 KB
testcase_04 738 ms 34844 KB
testcase_05 749 ms 34872 KB
testcase_06 20 ms 3064 KB
testcase_07 679 ms 32220 KB
testcase_08 428 ms 21660 KB
testcase_09 20 ms 3064 KB
testcase_10 716 ms 35420 KB
testcase_11 146 ms 9328 KB
testcase_12 22 ms 3064 KB
testcase_13 705 ms 34884 KB
testcase_14 721 ms 34896 KB
testcase_15 596 ms 29192 KB
testcase_16 312 ms 16600 KB
testcase_17 678 ms 31912 KB
testcase_18 627 ms 25628 KB
testcase_19 581 ms 25408 KB
testcase_20 638 ms 25624 KB
testcase_21 20 ms 3064 KB
testcase_22 97 ms 6760 KB
testcase_23 171 ms 10480 KB