QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225114 | #5502. Dazzling Mountain | chinskibronzord | RE | 10ms | 8164kb | Python3 | 1.6kb | 2023-10-23 23:45:40 | 2023-10-23 23:45:40 |
Judging History
answer
def toDykta(A):
dick = {}
for i in range(len(A)):
if A[i] not in dick:
dick[A[i]] = [i]
else:
dick[A[i]].append(i)
return dick
def test():
n = int(input().strip())
Asc = [set() for i in range(n)]
XValues = [1 for i in range(n)]
visited = [False for i in range(n)]
Father = [None for i in range(n)]
LeavesBelow = [0 for i in range(n)]
for i in range(n-1):
a,b = input().split(' ')
a = int(a)-1
b = int(b)-1
Asc[a].add(b)
Asc[b].add(a)
dfs(0, Asc, XValues, visited,Father)
for starting_point in range(n):
if (XValues[starting_point] == 1):
vertus = starting_point
while (vertus != None):
# print('Incrementing', vertus, 'leaves count')
LeavesBelow[vertus] += 1
vertus = Father[vertus]
Xdick = toDykta(XValues)
# print(Xdick)
returns = []
for dval in Xdick:
if(sum([LeavesBelow[qq] for qq in Xdick[dval]])==LeavesBelow[0]):
returns.append(dval)
print(len(returns))
returns.sort()
for r in returns:
print(r, end=' ')
def dfs(starting_point, Asc, XValues, visited,Father):
visited[starting_point] = True
for vert in Asc[starting_point]:
if( not visited[vert]):
dfs(vert, Asc, XValues, visited,Father)
Father[vert] = starting_point
XValues[starting_point]+=XValues[vert]
Z = int(input().strip())
for i in range(Z):
test()
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 10ms
memory: 8164kb
input:
1 9 1 2 2 3 3 4 3 5 2 6 6 7 7 8 7 9
output:
4 1 3 8 9
result:
ok 2 lines
Test #2:
score: -100
Dangerous Syscalls
input:
10000 906 675 189 555 889 491 97 791 419 175 694 713 842 788 513 159 354 670 815 652 546 253 87 89 278 563 429 522 900 202 657 331 865 35 605 735 532 612 471 657 386 7 886 856 164 224 777 73 534 481 631 711 698 240 465 115 181 191 825 311 155 709 501 207 849 294 546 591 682 96 405 210 696 861 13 781...
output:
63 1 3 4 34 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 6 1 2 3 4 5 11 28 1 2 3 4 5 6 15 16 17 18 19 20 21 2...