Submission #1030579


Source Code Expand

inputs=lambda:map(int,raw_input().split())
n, m = inputs()
es = [inputs()[::-1] for i in xrange(m)]
es.sort()
parent = range(n+1)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = root(parent[x])
    return parent[x]
def unite(x, y):
    px = root(x)
    py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py
su = 0
g = [[] for i in xrange(n+1)]
for c, a, b in es:
    if root(a) != root(b):
        unite(a, b)
        su += c
        g[a].append((b, c))
        g[b].append((a, c))

import sys
sys.setrecursionlimit(100000)
dic = {}
def dfs(s, v, prev, cost):
    dic[s,v] = cost
    for e, c in g[v]:
        if prev != e:
            dfs(s, e, v, max(cost, c))
for i in xrange(n):
    dfs(i+1, i+1, -1, 0)
for i in xrange(input()):
    s, t = inputs()
    print su-dic[s,t]

Submission Info

Submission Time
Task A - Graph
User yaketake08
Language Python (2.7.6)
Score 0
Code Size 869 Byte
Status TLE
Exec Time 3187 ms
Memory 312780 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 0 / 200 0 / 300 0 / 200
Status
AC × 2
AC × 3
TLE × 9
AC × 4
TLE × 17
AC × 4
TLE × 25
Set Name Test Cases
Sample sample_1.txt, sample_2.txt
subtask1 sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt
All sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt
Case Name Status Exec Time Memory
sample_1.txt AC 17 ms 2696 KB
sample_2.txt AC 17 ms 2696 KB
subtask_1_1.txt AC 30 ms 4288 KB
subtask_1_10.txt TLE 3177 ms 288036 KB
subtask_1_11.txt AC 17 ms 2696 KB
subtask_1_2.txt TLE 3177 ms 273500 KB
subtask_1_3.txt TLE 3169 ms 151096 KB
subtask_1_4.txt TLE 3178 ms 284328 KB
subtask_1_5.txt TLE 3174 ms 252080 KB
subtask_1_6.txt TLE 3179 ms 308660 KB
subtask_1_7.txt TLE 3171 ms 171008 KB
subtask_1_8.txt TLE 3176 ms 267560 KB
subtask_1_9.txt TLE 3175 ms 252984 KB
subtask_2_1.txt TLE 3173 ms 200344 KB
subtask_2_2.txt TLE 3171 ms 200264 KB
subtask_2_3.txt TLE 3171 ms 200312 KB
subtask_2_4.txt TLE 3173 ms 200196 KB
subtask_2_5.txt TLE 3177 ms 286760 KB
subtask_2_6.txt TLE 3176 ms 265768 KB
subtask_2_7.txt TLE 3180 ms 312780 KB
subtask_2_8.txt TLE 3170 ms 163084 KB
subtask_3_1.txt TLE 3170 ms 166576 KB
subtask_3_2.txt TLE 3169 ms 146200 KB
subtask_3_3.txt TLE 3177 ms 284968 KB
subtask_3_4.txt TLE 3176 ms 252920 KB
subtask_3_5.txt TLE 3178 ms 288080 KB
subtask_3_6.txt TLE 3187 ms 305988 KB
subtask_3_7.txt TLE 3169 ms 150304 KB
subtask_3_8.txt TLE 3171 ms 200284 KB