QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#123365	#5663. Tangle: A DAG for storing transactions	GenshinImpactsFault^#	AC ✓	421ms	3972kb	C++14	1.0kb	2023-07-12 13:47:15	2023-07-12 13:47:18

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-07-12 13:47:18]
评测

测评结果：AC
用时：421ms
内存：3972kb

查看

[2023-07-12 13:47:15]
提交

answer

#include <bits/stdc++.h>
using namespace std;
vector<int> G[10010];
int val[10010];
int q[10010], fr, re;
bool vis[10010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, lim;
    cin >> n >> lim;
    for(int i = 1; i <= n; ++ i) {
        int x, y, z;
        cin >> x >> y >> z;
        cin >> val[x];
        G[y].push_back(x);
        G[z].push_back(x);
    }
    int cnt = 0;
    for(int i = 2; i <= n; ++ i) {
        fr = re = 1;
        q[fr] = i;
        for(int j = 1; j <= n + 1; ++ j) {
            vis[j] = 0;
        }
        int sum = 0;
        while(fr <= re) {
            int x = q[fr ++];
            sum += val[x];
            for(auto j : G[x]) {
                if(!vis[j]) {
                    // cerr << x << " " 
                    vis[j] = 1;
                    q[++ re] = j;
                }
            }
        }
        if(sum >= lim) {
            ++ cnt;
            cout << i << " " << sum << endl;
        }
    }
    cout << cnt << endl;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3644kb

input:

output:

2 18
3 14
2

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 1ms

memory: 3676kb

input:

output:

result:

ok 7 lines

Test #3:

score: 0

Accepted

time: 1ms

memory: 3580kb

input:

output:

result:

ok 6 lines

Test #4:

score: 0

Accepted

time: 1ms

memory: 3736kb

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:

result:

ok 10 lines

Test #5:

score: 0

Accepted

time: 1ms

memory: 3644kb

input:

output:

result:

ok single line: '0'

Test #6:

score: 0

Accepted

time: 140ms

memory: 3972kb

input:

output:

result:

ok 512 lines

Test #7:

score: 0

Accepted

time: 421ms

memory: 3928kb

input:

output:

result:

ok 817 lines

Test #8:

score: 0

Accepted

time: 121ms

memory: 3776kb

input:

output:

result:

ok 1778 lines

Test #9:

score: 0

Accepted

time: 98ms

memory: 3860kb

input:

output:

result:

ok 966 lines