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 |
|
|
|
|
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 |