QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#186198#5663. Tangle: A DAG for storing transactionsBUET_POTATOES#AC ✓68ms16200kbC++20814b2023-09-23 12:58:332023-09-23 12:58:34

Judging History

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

  • [2023-09-23 12:58:34]
  • 评测
  • 测评结果：AC
  • 用时：68ms
  • 内存：16200kb
查看
  • [2023-09-23 12:58:33]
  • 提交

answer


#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 5;
bitset<N> bs[N];
vector<int> adj[N];
int cost[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, th;
    cin >> n >> th;
    for(int i = 0; i < n; i++){
        int x, y, z, w;
        cin >> x >> y >> z >> w;
        adj[y].push_back(x);
        adj[z].push_back(x);
        cost[x] = w;
    }

    for(int i = n + 1; i >= 0; i--){
        bs[i][i] = 1;
        for(auto x : adj[i])bs[i] |= bs[x];
    }
    int ans = 0;
    for(int i = 2; i <= n + 1; i++){
        int sum = 0;
        for(int j = 0; j <= n + 1; j++)if(bs[i][j])sum += cost[j];
        if(sum >= th){
            cout << i << ' ' << sum << "\n";
            ans++;
        }
    }
    cout << ans << "\n";
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3844kb

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: 1ms
memory: 3792kb

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: 1ms
memory: 3936kb

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: 1ms
memory: 3900kb

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: 0ms
memory: 3940kb

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: 24ms
memory: 12376kb

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: 0
Accepted
time: 68ms
memory: 16200kb

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:

2 29905
3 29901
4 29880
5 29856
6 29841
7 29854
8 29755
9 29866
10 29821
11 29433
12 29770
13 29808
14 29843
15 29727
16 29665
17 29838
18 29768
19 29717
20 29809
21 29657
22 29750
23 29700
24 29759
25 29755
26 29664
27 29671
28 29432
29 29680
30 29371
31 29498
32 29015
33 29701
34 29629
35 29650
36...

result:

ok 817 lines

Test #8:

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

input:

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

output:

2 14958
3 14921
4 14922
5 14898
6 14927
7 14738
8 14746
9 14734
10 14886
11 14557
12 14877
13 14742
14 14667
15 14475
16 14881
17 14597
18 14813
19 14478
20 14663
21 14861
22 14854
23 14731
24 14678
25 14713
26 14493
27 14734
28 14482
29 14776
30 14780
31 14537
32 11962
33 14476
34 14663
35 14481
36...

result:

ok 1778 lines

Test #9:

score: 0
Accepted
time: 14ms
memory: 11156kb

input:

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

output:

2 15127
3 15118
4 15114
5 15089
6 15049
7 14918
8 15027
9 14900
10 14894
11 15076
12 14983
13 15037
14 15055
15 15031
16 13392
17 15009
18 15022
19 15021
20 14982
21 14903
22 14959
23 14812
24 14503
25 14768
26 14905
27 14805
28 14880
29 14963
30 14181
31 14837
32 14871
33 14903
34 14728
35 14799
36...

result:

ok 966 lines
English 繁體中文 简体中文

服务器时间: 2024-12-11 22:24:00 | 开源项目