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
Task D - Decayed Bridges
User Syuko4omi
Language Python3 (3.4.3)
Score 400
Code Size 869 Byte
Status
Exec Time 749 ms
Memory 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