Submission #1030592
Source Code Expand
inputs=lambda:map(int,raw_input().split()) n, m = inputs() es = [inputs() for i in xrange(m)] es.sort(key=lambda x:x[-1]) 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 a, b, c 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 | PyPy2 (5.6.0) |
Score | 0 |
Code Size | 881 Byte |
Status | TLE |
Exec Time | 3196 ms |
Memory | 572372 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 200 | 0 / 300 | 0 / 200 | ||||||||||||||
Status |
|
|
|
|
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 | 51 ms | 9968 KB |
sample_2.txt | AC | 38 ms | 8944 KB |
subtask_1_1.txt | AC | 165 ms | 23324 KB |
subtask_1_10.txt | TLE | 3181 ms | 424900 KB |
subtask_1_11.txt | AC | 39 ms | 8944 KB |
subtask_1_2.txt | TLE | 3194 ms | 536020 KB |
subtask_1_3.txt | TLE | 3181 ms | 371672 KB |
subtask_1_4.txt | TLE | 3192 ms | 475316 KB |
subtask_1_5.txt | TLE | 3193 ms | 500684 KB |
subtask_1_6.txt | TLE | 3185 ms | 414532 KB |
subtask_1_7.txt | TLE | 3181 ms | 371120 KB |
subtask_1_8.txt | TLE | 3191 ms | 475832 KB |
subtask_1_9.txt | TLE | 3191 ms | 459452 KB |
subtask_2_1.txt | TLE | 3181 ms | 322520 KB |
subtask_2_2.txt | TLE | 3180 ms | 341644 KB |
subtask_2_3.txt | TLE | 3181 ms | 371676 KB |
subtask_2_4.txt | TLE | 3179 ms | 370264 KB |
subtask_2_5.txt | TLE | 3191 ms | 473272 KB |
subtask_2_6.txt | TLE | 3194 ms | 534736 KB |
subtask_2_7.txt | TLE | 3185 ms | 415044 KB |
subtask_2_8.txt | TLE | 3182 ms | 372696 KB |
subtask_3_1.txt | TLE | 3181 ms | 322612 KB |
subtask_3_2.txt | TLE | 3180 ms | 320688 KB |
subtask_3_3.txt | TLE | 3196 ms | 572372 KB |
subtask_3_4.txt | TLE | 3187 ms | 408888 KB |
subtask_3_5.txt | TLE | 3188 ms | 422468 KB |
subtask_3_6.txt | TLE | 3185 ms | 396372 KB |
subtask_3_7.txt | TLE | 3178 ms | 324952 KB |
subtask_3_8.txt | TLE | 3178 ms | 374488 KB |