编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#31655 #2070. 选课 Time Limit Exceeded 0 7596 ms 27740 K Python 3 / 2.1 K banned24 2025-03-16 19:03:06
import sys
sys.setrecursionlimit(200000)

def dfs_iterative(start, adj, credit, dp, visited):
    stack = [start]
    parent = [-1] * len(adj)
    order = []
    
    while stack:
        node = stack[-1]
        if visited[node] == 0:
            visited[node] = 1
            order.append(node)
            for neighbor in adj[node]:
                if visited[neighbor] == 0:  # 还没有访问过
                    parent[neighbor] = node
                    stack.append(neighbor)
        else:
            stack.pop()

    # 处理DFS结果
    for u in reversed(order):
        dp[u][0] = 0  # 不选u
        dp[u][1] = credit[u]  # 选u时的初始学分是该课程的学分
        for v in adj[u]:
            if v != parent[u]:
                dp[u][0] += max(dp[v][0], dp[v][1])  # 如果不选u,则v可以选也可以不选
                dp[u][1] += dp[v][0]  # 如果选u,则v不能选

def main():
    # 读取输入
    n = int(input())
    credit = [0] * n
    for i in range(n):
        credit[i] = int(input())
    
    # 邻接表存储图
    adj = [[] for _ in range(n)]
    
    # 读取冲突关系并构建图
    for i in range(n):
        data = list(map(int, input().split()))
        Ai = data[0]
        for j in range(1, Ai + 1):
            adj[i].append(data[j] - 1)  # 课程编号从1开始,转换为0-based
            adj[data[j] - 1].append(i)  # 无向图
    
    # DP数组,dp[u][0]表示不选u时的最大学分,dp[u][1]表示选u时的最大学分
    dp = [[0, 0] for _ in range(n)]
    visited = [0] * n  # 0: 未访问,1: 正在访问,2: 已访问
    total_max_credits = 0
    
    # 遍历每个连通分量
    for i in range(n):
        if visited[i] == 0:  # 如果课程i没有被访问过
            dfs_iterative(i, adj, credit, dp, visited)
            # 对于每个连通分量的根节点,选择dp[u][0]和dp[u][1]中的较大者
            total_max_credits += max(dp[i][0], dp[i][1])
    
    print(total_max_credits)

if __name__ == "__main__":
    main()
子任务 #1
Time Limit Exceeded
得分:0
测试点 #1
Time Limit Exceeded
得分:0
用时:1040 ms
内存:27608 KiB

输入文件(a1.in

64546
346
911
232
260
204
354
770
686
656
180
492
760
332
73
994
129
292
221
732
<1304086 bytes omitted>

答案文件(a1.out

21980830

用户输出

359028438254
测试点 #2
Time Limit Exceeded
得分:0
用时:1055 ms
内存:27740 KiB

输入文件(a2.in

87763
360
122
644
448
64
834
996
456
514
928
337
622
831
299
150
359
616
816
573
<1785910 bytes omitted>

答案文件(a2.out

29779119
测试点 #3
Time Limit Exceeded
得分:0
用时:1055 ms
内存:24980 KiB

输入文件(a3.in

97101
785
659
469
214
368
744
560
280
670
968
816
272
430
41
500
483
72
216
714

<1980327 bytes omitted>

答案文件(a3.out

33348125
测试点 #4
Time Limit Exceeded
得分:0
用时:1004 ms
内存:24784 KiB

输入文件(a4.in

96463
15
109
882
404
711
196
826
474
68
958
551
512
664
306
99
868
80
392
1000
5
<1967031 bytes omitted>

答案文件(a4.out

32960896
测试点 #5
Time Limit Exceeded
得分:0
用时:1005 ms
内存:23464 KiB

输入文件(a5.in

84245
394
737
934
484
602
32
127
444
543
384
860
925
416
248
896
432
198
964
400
<1712626 bytes omitted>

答案文件(a5.out

28721378
测试点 #6
Wrong Answer
得分:0
用时:482 ms
内存:15376 KiB

输入文件(a6.in

32637
135
269
88
586
80
410
895
360
898
480
37
686
182
520
877
879
124
167
932
4
<644317 bytes omitted>

答案文件(a6.out

11132180

用户输出

45082199992

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #7
Wrong Answer
得分:0
用时:968 ms
内存:26072 KiB

输入文件(a7.in

60741
802
467
361
954
776
84
314
830
338
187
984
625
182
638
194
530
298
546
710
<1225125 bytes omitted>

答案文件(a7.out

20739417

用户输出

1550182707086

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #8
Wrong Answer
得分:0
用时:233 ms
内存:8576 KiB

输入文件(a8.in

15201
908
169
997
372
674
852
20
800
436
627
620
732
866
516
456
620
806
422
260
<288163 bytes omitted>

答案文件(a8.out

5185111

用户输出

15943257138

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #9
Wrong Answer
得分:0
用时:433 ms
内存:13584 KiB

输入文件(a9.in

28101
858
8
80
704
892
252
373
456
748
158
520
237
7
866
976
16
539
288
960
420
<551205 bytes omitted>

答案文件(a9.out

9617080

用户输出

34081360138

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #10
Wrong Answer
得分:0
用时:321 ms
内存:10672 KiB

输入文件(a10.in

20685
792
775
818
562
12
216
332
200
872
338
111
432
388
298
96
712
84
256
577
3
<399364 bytes omitted>

答案文件(a10.out

7062131

用户输出

59699627176

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0