Submission #8411919
Source Code Expand
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines N = int(readline()) data = read().split() m = map(int,data[:-1]) XY = zip(m,m) C = [0] + [1 * (x == ord('W')) for x in data[-1]] graph = [set() for _ in range(N+1)] for x,y in XY: graph[x].add(y) graph[y].add(x) deg = [len(x) for x in graph] b_leaf = [i for i in range(N+1) if deg[i] == 1 and not C[i]] while b_leaf: x = b_leaf.pop() for y in graph[x]: graph[y].remove(x) deg[y] -= 1 if deg[y] == 1 and not C[y]: b_leaf.append(y) deg[x] = 0 graph[x].clear() V = set(i for i,E in enumerate(graph) if E) if len(V) <= 2: print(len(V)) exit() root = None for v in V: if deg[v] > 1: root = v break parent = [0] * (N+1) order = [] stack = [root] while stack: x = stack.pop() order.append(x) for y in graph[x]: if y == parent[x]: continue parent[y] = x stack.append(y) """ ・Euler tourの状態から、パスをひとつ除く ・葉と葉を結ぶとしてよい。通ると2コスト安くなる点がある """ for i in range(N+1): C[i] ^= (1°[i]) cost_full = sum(deg) + sum(C) # C[i] == 1 となる i を最もたくさん含むパスを探す opt = 0 dp = [0] * (N+1) for v in order[::-1]: if deg[v] == 1: continue arr = sorted((dp[w] for w in graph[v] if w != parent[v]),reverse = True) + [0] x = arr[0] + arr[1] + C[v] if opt < x: opt = x dp[v] = arr[0] + C[v] answer = cost_full - 2 * opt print(answer)
Submission Info
Submission Time | |
---|---|
Task | F - Monochrome Cat |
User | maspy |
Language | Python (3.4.3) |
Score | 0 |
Code Size | 1687 Byte |
Status | WA |
Exec Time | 689 ms |
Memory | 59648 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 800 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt, 1_064.txt, 1_065.txt, 1_066.txt, 1_067.txt, 1_068.txt, 1_069.txt, 1_070.txt, 1_071.txt, 1_072.txt, 1_073.txt, 1_074.txt, 1_075.txt, 1_076.txt, 1_077.txt, 1_078.txt, 1_079.txt, 1_080.txt, 1_081.txt, 1_082.txt, 1_083.txt, 1_084.txt, 1_085.txt, 1_086.txt, 1_087.txt, 1_088.txt, 1_089.txt, 1_090.txt, 1_091.txt, 1_092.txt, 1_093.txt, 1_094.txt, 1_095.txt, 1_096.txt, 1_097.txt, 1_098.txt, 1_099.txt, 1_100.txt, 1_101.txt, 1_102.txt, 1_103.txt, 1_104.txt, 1_105.txt, 1_106.txt, 1_107.txt, 1_108.txt, 1_109.txt, 1_110.txt, 1_111.txt, 1_112.txt, 1_113.txt, 1_114.txt, 1_115.txt, 1_116.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 18 ms | 3192 KB |
0_001.txt | AC | 18 ms | 3192 KB |
0_002.txt | AC | 18 ms | 3192 KB |
0_003.txt | AC | 17 ms | 3192 KB |
1_003.txt | WA | 17 ms | 3192 KB |
1_004.txt | WA | 18 ms | 3192 KB |
1_005.txt | AC | 17 ms | 3192 KB |
1_006.txt | WA | 18 ms | 3192 KB |
1_007.txt | WA | 17 ms | 3192 KB |
1_008.txt | AC | 18 ms | 3192 KB |
1_009.txt | AC | 17 ms | 3192 KB |
1_010.txt | AC | 18 ms | 3192 KB |
1_011.txt | AC | 17 ms | 3192 KB |
1_012.txt | WA | 18 ms | 3192 KB |
1_013.txt | AC | 18 ms | 3192 KB |
1_014.txt | AC | 18 ms | 3192 KB |
1_015.txt | AC | 17 ms | 3192 KB |
1_016.txt | AC | 17 ms | 3192 KB |
1_017.txt | AC | 18 ms | 3192 KB |
1_018.txt | WA | 17 ms | 3192 KB |
1_019.txt | AC | 18 ms | 3192 KB |
1_020.txt | AC | 18 ms | 3192 KB |
1_021.txt | AC | 18 ms | 3192 KB |
1_022.txt | AC | 18 ms | 3192 KB |
1_023.txt | AC | 17 ms | 3192 KB |
1_024.txt | WA | 18 ms | 3192 KB |
1_025.txt | AC | 18 ms | 3192 KB |
1_026.txt | AC | 18 ms | 3192 KB |
1_027.txt | AC | 17 ms | 3192 KB |
1_028.txt | AC | 18 ms | 3192 KB |
1_029.txt | AC | 17 ms | 3192 KB |
1_030.txt | WA | 18 ms | 3192 KB |
1_031.txt | AC | 17 ms | 3192 KB |
1_032.txt | AC | 18 ms | 3192 KB |
1_033.txt | AC | 18 ms | 3192 KB |
1_034.txt | AC | 18 ms | 3192 KB |
1_035.txt | AC | 18 ms | 3192 KB |
1_036.txt | WA | 18 ms | 3192 KB |
1_037.txt | AC | 18 ms | 3192 KB |
1_038.txt | AC | 18 ms | 3192 KB |
1_039.txt | AC | 18 ms | 3192 KB |
1_040.txt | AC | 18 ms | 3192 KB |
1_041.txt | AC | 18 ms | 3192 KB |
1_042.txt | WA | 18 ms | 3192 KB |
1_043.txt | AC | 18 ms | 3192 KB |
1_044.txt | AC | 18 ms | 3192 KB |
1_045.txt | AC | 229 ms | 23136 KB |
1_046.txt | AC | 272 ms | 26792 KB |
1_047.txt | AC | 337 ms | 43616 KB |
1_048.txt | WA | 240 ms | 33968 KB |
1_049.txt | AC | 450 ms | 38224 KB |
1_050.txt | AC | 431 ms | 36732 KB |
1_051.txt | AC | 281 ms | 43880 KB |
1_052.txt | AC | 72 ms | 12176 KB |
1_053.txt | AC | 265 ms | 43096 KB |
1_054.txt | WA | 106 ms | 20636 KB |
1_055.txt | AC | 270 ms | 43280 KB |
1_056.txt | WA | 144 ms | 25636 KB |
1_057.txt | AC | 25 ms | 3956 KB |
1_058.txt | AC | 243 ms | 26352 KB |
1_059.txt | AC | 124 ms | 17668 KB |
1_060.txt | WA | 236 ms | 34216 KB |
1_061.txt | AC | 474 ms | 44156 KB |
1_062.txt | AC | 219 ms | 25212 KB |
1_063.txt | AC | 279 ms | 36072 KB |
1_064.txt | AC | 175 ms | 24448 KB |
1_065.txt | AC | 33 ms | 5620 KB |
1_066.txt | WA | 248 ms | 39720 KB |
1_067.txt | AC | 91 ms | 12732 KB |
1_068.txt | AC | 185 ms | 27836 KB |
1_069.txt | AC | 136 ms | 17280 KB |
1_070.txt | AC | 218 ms | 25896 KB |
1_071.txt | AC | 269 ms | 38704 KB |
1_072.txt | WA | 168 ms | 24920 KB |
1_073.txt | AC | 58 ms | 7924 KB |
1_074.txt | AC | 40 ms | 5748 KB |
1_075.txt | AC | 224 ms | 25284 KB |
1_076.txt | AC | 493 ms | 48476 KB |
1_077.txt | AC | 255 ms | 37280 KB |
1_078.txt | WA | 92 ms | 15468 KB |
1_079.txt | AC | 213 ms | 25052 KB |
1_080.txt | AC | 213 ms | 26176 KB |
1_081.txt | AC | 681 ms | 57240 KB |
1_082.txt | AC | 685 ms | 57236 KB |
1_083.txt | AC | 334 ms | 44344 KB |
1_084.txt | WA | 342 ms | 44344 KB |
1_085.txt | AC | 689 ms | 54040 KB |
1_086.txt | AC | 672 ms | 57240 KB |
1_087.txt | AC | 376 ms | 59648 KB |
1_088.txt | AC | 361 ms | 53108 KB |
1_089.txt | AC | 331 ms | 51584 KB |
1_090.txt | WA | 312 ms | 51584 KB |
1_091.txt | AC | 376 ms | 59648 KB |
1_092.txt | AC | 312 ms | 51584 KB |
1_093.txt | AC | 581 ms | 55832 KB |
1_094.txt | AC | 559 ms | 51632 KB |
1_095.txt | AC | 332 ms | 44932 KB |
1_096.txt | WA | 336 ms | 44944 KB |
1_097.txt | AC | 585 ms | 54296 KB |
1_098.txt | AC | 541 ms | 50092 KB |
1_099.txt | AC | 506 ms | 57096 KB |
1_100.txt | AC | 456 ms | 51188 KB |
1_101.txt | AC | 328 ms | 48008 KB |
1_102.txt | WA | 330 ms | 48012 KB |
1_103.txt | AC | 508 ms | 57224 KB |
1_104.txt | AC | 414 ms | 50096 KB |
1_105.txt | AC | 618 ms | 54424 KB |
1_106.txt | AC | 534 ms | 49736 KB |
1_107.txt | AC | 367 ms | 45464 KB |
1_108.txt | WA | 342 ms | 45572 KB |
1_109.txt | AC | 554 ms | 54424 KB |
1_110.txt | AC | 493 ms | 48976 KB |
1_111.txt | AC | 553 ms | 54416 KB |
1_112.txt | AC | 526 ms | 49740 KB |
1_113.txt | AC | 336 ms | 45460 KB |
1_114.txt | WA | 336 ms | 45580 KB |
1_115.txt | AC | 553 ms | 54412 KB |
1_116.txt | AC | 496 ms | 48976 KB |