Contest Duration: - (local time) (100 minutes) Back to Home

Submission #9619555

Source Code Expand

Copy
```import sys

import numpy as np

AB = list(list(map(int,readline().split())) for _ in range(N-1))
UV = list(list(map(int,readline().split())) for _ in range(M))

graph = [[] for _ in range(N+1)]
for i, (a,b) in enumerate(AB):
graph[a].append((b,i))
graph[b].append((a,i))

def get_path(U,V):
INF = 100
visited = [False] * (N+1)
pred = [None] * (N+1)
stack = [U]
visited[U] = True
while stack:
v = stack.pop()
for w, i in graph[v]:
if visited[w]:
continue
visited[w] = True
pred[w] = (v,i)
stack.append(w)
path = 0
w = V
while w != U:
v,i = pred[w]
w = v
path += 1<<i
return path

condition_path = [get_path(u,v) for u,v in UV]

S = np.zeros(1<<M,np.int64)
sgn = np.ones(1<<M,np.int64)
for i in range(M):
S[1<<i:1<<(i+1)] = S[:1<<i] | condition_path[i]
sgn[1<<i:1<<(i+1)] = -sgn[:1<<i]

def popcnt(n):
c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
return c

n_edges = popcnt(S)

x = 1<<(N-1-n_edges)

#### Submission Info

Submission Time 2020-01-19 21:40:36+0900 F - Tree and Constraints maspy Python (3.4.3) 600 1651 Byte AC 230 ms 61600 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
 AC × 4
 AC × 27
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All dense_01.txt, dense_02.txt, dense_03.txt, dense_04.txt, dense_05.txt, large_ans.txt, line_01.txt, line_02.txt, line_03.txt, no_overlap.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, star_01.txt, star_02.txt, star_03.txt
Case Name Status Exec Time Memory
dense_01.txt AC 226 ms 61600 KB
dense_02.txt AC 152 ms 14000 KB
dense_03.txt AC 150 ms 13992 KB
dense_04.txt AC 229 ms 61600 KB
dense_05.txt AC 152 ms 13992 KB
large_ans.txt AC 149 ms 12480 KB
line_01.txt AC 228 ms 61600 KB
line_02.txt AC 228 ms 61600 KB
line_03.txt AC 228 ms 61596 KB
no_overlap.txt AC 229 ms 61596 KB
random_01.txt AC 185 ms 37016 KB
random_02.txt AC 228 ms 61584 KB
random_03.txt AC 185 ms 37024 KB
random_04.txt AC 230 ms 61588 KB
random_05.txt AC 185 ms 37028 KB
random_06.txt AC 229 ms 61596 KB
random_07.txt AC 185 ms 36976 KB
random_08.txt AC 185 ms 37024 KB
random_09.txt AC 228 ms 61588 KB
random_10.txt AC 229 ms 61552 KB
sample_01.txt AC 148 ms 12480 KB
sample_02.txt AC 148 ms 12492 KB
sample_03.txt AC 150 ms 12444 KB
sample_04.txt AC 150 ms 12492 KB
star_01.txt AC 229 ms 61600 KB
star_02.txt AC 227 ms 61600 KB
star_03.txt AC 228 ms 61588 KB