QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#642052#5663. Tangle: A DAG for storing transactionsvwxyzTL 2729ms11580kbPython3563b2024-10-15 09:19:292024-10-15 09:19:30

Judging History

你现在查看的是最新测评结果

  • [2024-10-15 09:19:30]
  • 评测
  • 测评结果：TL
  • 用时：2729ms
  • 内存：11580kb
查看
  • [2024-10-15 09:19:29]
  • 提交

answer

N,X=map(int,input().split())
N+=2
graph=[[] for x in range(N)]
W=[0,0]
for i in range(N-2):
    x,y,z,w=map(int,input().split())
    graph[y].append(x)
    graph[z].append(x)
    W.append(w)
cnt=0
for s in range(2,N):
    seen=[False]*N
    queue=[s]
    seen[s]=True
    while queue:
        x=queue.pop()
        for y in graph[x]:
            if seen[y]:
                continue
            seen[y]=True
            queue.append(y)
    S=sum(W[x] for x in range(N) if seen[x])
    if S>=X:
        print(s,S)
        cnt+=1
print(cnt)
Source code, Language: Python3

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 10620kb

input:

6 12
2 0 1 3
3 0 2 2
4 1 2 1
5 2 3 3
6 3 4 4
7 3 5 5

output:

2 18
3 14
2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 15ms
memory: 10528kb

input:

21 20
2 0 1 2
3 1 0 5
4 1 0 2
5 2 1 1
6 1 3 1
7 5 4 1
8 3 7 5
9 2 4 1
10 4 9 1
11 9 4 5
12 4 8 2
13 3 12 2
14 2 10 5
15 11 12 4
16 3 9 2
17 1 16 4
18 0 7 3
19 11 5 2
20 14 4 5
21 19 5 2
22 18 9 4

output:

2 51
3 25
4 50
5 26
7 21
9 35
6

result:

ok 7 lines

Test #3:

score: 0
Accepted
time: 4ms
memory: 10604kb

input:

99 250
2 1 0 1
3 0 2 2
4 3 2 1
5 4 3 4
6 1 2 3
7 5 0 1
8 0 7 2
9 0 8 3
10 3 4 5
11 1 4 4
12 5 6 3
13 12 8 2
14 13 2 3
15 4 10 5
16 5 6 1
17 7 10 1
18 2 5 5
19 9 7 4
20 16 12 5
21 6 3 1
22 7 9 1
23 13 11 1
24 12 9 3
25 7 22 3
26 10 20 5
27 11 12 2
28 26 9 5
29 18 6 5
30 13 17 4
31 25 12 4
32 31 20 3
...

output:

2 297
3 293
4 290
5 275
6 255
5

result:

ok 6 lines

Test #4:

score: 0
Accepted
time: 16ms
memory: 10600kb

input:

100 200
2 0 1 2
3 2 0 5
4 2 0 2
5 4 0 4
6 2 5 4
7 5 0 5
8 4 2 4
9 2 6 4
10 0 9 3
11 2 8 2
12 4 2 1
13 7 5 3
14 3 4 5
15 10 0 5
16 6 13 1
17 9 10 4
18 12 6 4
19 17 12 1
20 10 8 4
21 2 4 2
22 6 17 2
23 3 12 4
24 21 12 2
25 14 10 5
26 14 21 4
27 13 11 1
28 21 6 1
29 10 5 3
30 26 6 1
31 13 8 5
32 25 19 ...

output:

2 303
3 210
4 296
5 270
6 252
9 225
10 221
12 222
14 201
9

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 18ms
memory: 10740kb

input:

199 800
2 1 0 1
3 0 2 2
4 3 0 4
5 4 0 3
6 4 3 2
7 0 2 1
8 5 7 3
9 3 0 2
10 1 9 4
11 5 2 4
12 9 4 3
13 7 12 2
14 10 0 1
15 1 6 2
16 5 11 5
17 4 15 4
18 4 14 5
19 11 0 1
20 3 13 5
21 3 4 2
22 20 14 2
23 14 1 5
24 7 19 5
25 13 17 4
26 10 23 5
27 17 12 4
28 12 13 5
29 24 1 4
30 19 7 4
31 18 22 5
32 17 1...

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 2729ms
memory: 11580kb

input:

5999 15000
2 0 1 2
3 2 1 1
4 3 1 4
5 1 2 5
6 4 1 1
7 2 6 3
8 4 1 5
9 7 8 2
10 0 4 4
11 3 2 1
12 8 1 1
13 10 3 2
14 1 0 3
15 13 1 3
16 0 4 5
17 6 8 2
18 1 6 1
19 5 2 2
20 4 6 5
21 8 0 2
22 9 20 4
23 17 7 4
24 17 0 1
25 23 3 4
26 12 15 1
27 15 5 3
28 17 25 2
29 17 24 3
30 28 9 2
31 22 6 2
32 12 9 3
33...

output:

2 18207
3 18198
4 18196
5 17811
6 18160
7 18147
8 18160
9 18108
10 18039
11 17672
12 17781
13 18035
14 15556
15 17938
16 18046
17 18138
18 17953
19 16110
20 18097
21 17976
22 18092
23 18113
24 18004
25 18001
26 17560
27 17707
28 17997
29 17998
30 16680
31 18085
32 17770
33 17680
34 17906
35 17902
36...

result:

ok 512 lines

Test #7:

score: -100
Time Limit Exceeded

input:

9999 25000
2 0 1 4
3 2 1 3
4 1 0 3
5 1 4 2
6 3 2 3
7 3 5 2
8 4 6 1
9 3 0 5
10 6 0 1
11 9 6 1
12 9 10 2
13 2 7 2
14 9 4 5
15 7 13 1
16 9 3 4
17 14 4 1
18 6 12 5
19 17 0 5
20 17 4 3
21 10 13 3
22 8 0 3
23 7 19 4
24 13 20 2
25 24 13 1
26 23 20 2
27 19 0 3
28 15 11 2
29 10 15 4
30 10 2 2
31 27 25 4
32 2...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-02 19:37:48 | OpenSource Project