QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#429841	#8724. September	MODDI	25	159ms	19308kb	C++20	2.1kb	2024-06-02 22:34:50	2024-06-02 22:34:51

Judging History

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

[2024-06-02 22:34:51]
评测

测评结果：25
用时：159ms
内存：19308kb

查看

[2024-06-02 22:34:50]
提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define pb push_back
#define mp make_pair
int in[100100], out[100100], sz[100100], timer = 0;
vi G[100100];
template <class T> class BIT {
private:
    int size;
    vector<T> bit;
    vector<T> arr;

public:
    BIT(int size) : size(size), bit(size + 1), arr(size) {}

    void set(int ind, int val) { add(ind, val - arr[ind]); }

    void add(int ind, int val) {
        arr[ind] += val;
        ind++;
        for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
    }

    T pref_sum(int ind) {
        ind++;
        T total = 0;
        for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
        return total;
    }
};

void dfs(int node, int prev){
    in[node] = timer++;
    sz[node] = 1;
    for(auto next : G[node]){
        if(next != prev){
            dfs(next, node);
            sz[node] += sz[next];
        }
    }
    out[node] = timer;
}
bool is_ancestor(int u, int v){
    return in[u] <= in[v] && out[u] >= out[v];
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>>S){
    if(M > 1)   return 0;
    for(int i = 0; i <= N; i++)  G[i].clear();
    memset(in, 0, sizeof in);
    memset(out, 0, sizeof out);
    memset(sz, 0, sizeof sz);
    timer = 0;
    for(int i = 1; i < F.size(); i++){
        G[F[i]].pb(i);
        G[i].pb(F[i]);
    }
    dfs(0, -1);
    BIT<long long> bit(N+10);
    int ans = 0, not_out = -1;
    for(auto idx : S[0]){
        bit.add(in[idx], 1);
        if(not_out == -1)   not_out = idx;
        else{
            if(is_ancestor(idx, not_out)){
                not_out = idx;
            }
        }
        ll end_sum = bit.pref_sum(out[not_out]-1);
        ll start_sum;
        if(in[not_out] == 0)    start_sum = 0;
        else start_sum = bit.pref_sum(in[not_out]-1 );
        if(end_sum - start_sum == sz[not_out]){
            ans++;
            not_out = -1;
        }
    }
    return ans;
}

源文件, 语言: C++20

详细

Subtask #1:

score: 11

Accepted

Test #1:

score: 11

Accepted

time: 2ms

memory: 6560kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
4
7 1
0 0 2 3 3 5
1 6 4 3 5 2
10 1
0 1 2 0 3 0 5 4 8
9 7 6 8 4 5 3 2 1
7 1
0 0 0 1 3 0
2 4 1 6 5 3
6 1
0 0 1 1 3
4 5 2 3 1

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
5
9
6
5

result:

ok 5 lines

Test #2:

score: 11

Accepted

time: 2ms

memory: 4816kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
4
7 1
0 1 0 2 4 0
3 6 5 2 4 1
10 1
0 0 0 0 2 1 3 3 6
5 9 6 4 7 2 3 8 1
7 1
0 0 2 0 2 2
3 5 6 2 1 4
6 1
0 0 1 2 0
3 4 2 1 5

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
5
8
6
5

result:

ok 5 lines

Test #3:

score: 11

Accepted

time: 0ms

memory: 4832kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
4
7 1
0 0 1 3 4 5
6 2 5 4 3 1
10 1
0 0 2 3 4 4 6 7 8
5 9 1 8 7 6 3 4 2
7 1
0 1 1 3 4 4
2 6 5 4 3 1
6 1
0 1 2 2 3
3 5 4 1 2

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
6
8
6
3

result:

ok 5 lines

Test #4:

score: 11

Accepted

time: 1ms

memory: 4932kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
4
7 1
0 0 1 2 4 4
6 5 4 1 3 2
10 1
0 1 2 3 4 5 6 7 7
8 9 7 5 6 2 4 3 1
7 1
0 1 2 2 4 5
3 6 4 5 1 2
6 1
0 0 1 2 4
5 4 2 3 1

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
5
6
4
5

result:

ok 5 lines

Test #5:

score: 11

Accepted

time: 1ms

memory: 5760kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
4
7 1
0 1 0 2 0 4
5 3 6 4 1 2
10 1
0 1 0 3 4 1 1 1 2
9 6 7 5 4 3 8 2 1
7 1
0 0 2 0 4 5
6 3 1 2 5 4
6 1
0 0 1 3 1
5 3 1 2 4

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
5
9
6
2

result:

ok 5 lines

Test #6:

score: 11

Accepted

time: 1ms

memory: 5968kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
4
7 1
0 1 2 2 2 5
6 4 5 3 1 2
10 1
0 0 1 0 1 2 4 4 4
7 9 6 5 3 2 4 1 8
7 1
0 1 1 0 2 5
6 4 2 5 3 1
6 1
0 0 2 2 1
3 5 4 2 1

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
5
7
5
5

result:

ok 5 lines

Test #7:

score: 11

Accepted

time: 0ms

memory: 6808kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
4
7 1
0 0 2 2 3 4
1 5 6 3 4 2
10 1
0 0 2 3 3 4 6 7 7
8 1 9 5 6 7 4 3 2
7 1
0 0 1 2 4 4
6 3 5 1 4 2
6 1
0 0 2 2 3
3 1 5 4 2

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
6
8
6
3

result:

ok 5 lines

Test #8:

score: 11

Accepted

time: 0ms

memory: 4756kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
4
7 1
0 0 1 2 4 5
6 3 5 1 2 4
10 1
0 0 2 2 3 4 5 6 8
9 7 8 6 5 4 1 3 2
7 1
0 1 1 2 3 5
4 6 2 3 5 1
6 1
0 0 2 3 3
5 4 1 3 2

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
5
9
5
5

result:

ok 5 lines

Subtask #2:

score: 0

Wrong Answer

Dependency #1:

100%

Accepted

Test #9:

score: 0

Wrong Answer

time: 0ms

memory: 3812kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
4
7 5
0 0 2 2 3 1
4 5 6 3 1 2
4 5 6 1 3 2
4 5 6 3 1 2
4 5 6 3 1 2
4 5 6 3 1 2
10 5
0 1 1 2 4 5 0 2 0
9 6 5 7 8 4 3 1 2
9 6 7 5 4 8 1 2 3
6 9 7 5 4 8 2 1 3
6 9 7 5 4 2 1 8 3
6 9 7 5 4 2 1 8 3
7 5
0 0 0 3 1 4
6 5 4 1 3 2
5 6 1 4 3 2
5 6 1 3 4 2
5 1 6 4 2 3
5 1 4 2 6 3
...

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
0
0
0
0

result:

wrong answer 2nd lines differ - expected: '5', found: '0'

Subtask #3:

score: 5

Accepted

Test #17:

score: 5

Accepted

time: 2ms

memory: 6004kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
53
10 1
0 1 2 3 4 5 6 7 8
9 8 7 6 5 4 3 2 1
10 1
0 1 2 3 4 5 6 7 8
9 7 8 5 6 4 3 2 1
10 1
0 1 2 3 4 5 6 7 8
8 9 7 5 6 3 2 4 1
10 1
0 1 2 3 4 5 6 7 8
8 9 6 7 5 4 3 2 1
10 1
0 1 2 3 4 5 6 7 8
8 9 7 5 6 3 4 2 1
10 1
0 1 2 3 4 5 6 7 8
9 8 7 6 5 4 2 3 1
10 1
0 1 2 3 4 5 6...

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
9
7
5
7
6
8
6
8
7
6
4
5
8
6
9
7
7
6
8
7
30
29
24
20
22
59
567
58
33
25
30
37
34
7
3
8
4
8
7
6
4
5
7
6
6
8
4
6
5
7
6
9
6

result:

ok 54 lines

Test #18:

score: 5

Accepted

time: 0ms

memory: 6464kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
53
10 1
0 1 2 3 4 5 6 7 8
9 8 7 6 5 4 2 3 1
10 1
0 1 2 3 4 5 6 7 8
8 9 7 6 5 4 3 2 1
10 1
0 1 2 3 4 5 6 7 8
8 9 5 7 6 3 1 2 4
10 1
0 1 2 3 4 5 6 7 8
9 7 8 6 5 4 3 1 2
10 1
0 1 2 3 4 5 6 7 8
8 9 7 6 5 4 3 2 1
10 1
0 1 2 3 4 5 6 7 8
9 8 6 7 3 4 5 1 2
10 1
0 1 2 3 4 5 6...

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
8
8
3
7
8
5
4
3
7
7
8
6
9
5
3
8
3
1
6
4
35
34
25
9
30
2
309
61
9
21
32
8
31
5
6
8
8
8
7
7
8
8
2
7
7
6
2
7
7
2
3
5
8

result:

ok 54 lines

Test #19:

score: 5

Accepted

time: 2ms

memory: 6036kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
53
10 1
0 1 2 3 4 5 6 7 8
9 8 7 6 5 4 2 3 1
10 1
0 1 2 3 4 5 6 7 8
9 7 6 8 4 3 2 1 5
10 1
0 1 2 3 4 5 6 7 8
9 8 7 6 5 4 3 2 1
10 1
0 1 2 3 4 5 6 7 8
9 8 6 7 5 3 4 2 1
10 1
0 1 2 3 4 5 6 7 8
9 7 8 5 6 4 3 2 1
10 1
0 1 2 3 4 5 6 7 8
9 8 7 6 5 4 3 2 1
10 1
0 1 2 3 4 5 6...

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
8
3
9
7
7
9
6
4
5
6
5
7
6
8
7
7
6
7
7
5
19
23
33
38
27
75
833
80
21
30
34
17
30
6
3
7
7
6
8
5
4
9
7
7
7
8
4
8
6
6
8
8
8

result:

ok 54 lines

Test #20:

score: 5

Accepted

time: 2ms

memory: 6048kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
53
10 1
0 1 2 3 4 5 6 7 8
9 8 6 7 2 5 3 1 4
10 1
0 1 2 3 4 5 6 7 8
5 7 9 2 6 4 3 1 8
10 1
0 1 2 3 4 5 6 7 8
9 7 8 6 5 4 3 2 1
10 1
0 1 2 3 4 5 6 7 8
8 9 7 6 5 4 2 3 1
10 1
0 1 2 3 4 5 6 7 8
7 8 6 5 4 1 3 9 2
10 1
0 1 2 3 4 5 6 7 8
8 9 7 6 4 5 3 2 1
10 1
0 1 2 3 4 5 6...

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
4
1
8
7
1
7
5
3
5
1
7
4
4
7
9
2
6
4
8
4
6
8
22
23
30
78
852
78
32
29
28
13
34
7
8
7
7
8
3
3
7
9
7
5
9
8
6
8
7
9
8
8
9

result:

ok 54 lines

Subtask #4:

score: 0

Wrong Answer

Dependency #1:

100%

Accepted

Dependency #3:

100%

Accepted

Test #21:

score: 9

Accepted

time: 0ms

memory: 6152kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
53
10 1
0 0 1 0 4 2 6 4 5
8 9 5 7 3 4 1 6 2
10 1
0 1 2 0 3 1 6 5 2
4 9 8 5 7 3 6 2 1
10 1
0 0 2 0 0 4 6 0 6
8 7 5 1 2 3 9 6 4
10 1
0 1 2 2 2 1 3 0 4
8 5 6 7 4 3 9 2 1
10 1
0 0 0 0 3 5 6 0 5
1 9 4 8 7 2 6 3 5
10 1
0 1 2 1 0 1 3 5 1
4 7 6 3 8 5 2 9 1
10 1
0 0 2 2 3 0 3...

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
9
9
8
7
8
9
9
9
9
9
8
7
8
9
9
9
9
5
8
9
38
38
38
38
37
89
998
99
39
38
38
39
37
8
9
5
6
9
9
8
9
9
8
9
8
5
7
8
8
9
9
8
9

result:

ok 54 lines

Test #22:

score: 0

Wrong Answer

time: 3ms

memory: 6688kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
53
10 1
0 0 0 0 2 2 4 4 6
7 5 3 8 9 4 6 2 1
10 1
0 1 0 1 0 1 4 3 5
9 2 8 5 4 7 3 1 6
10 1
0 1 2 3 1 5 3 1 5
9 4 6 8 5 7 2 3 1
10 1
0 0 1 3 4 3 2 4 4
8 6 7 5 9 2 4 3 1
10 1
0 1 0 1 3 2 3 6 7
1 3 8 2 9 7 5 4 6
10 1
0 1 2 3 0 3 6 0 5
4 8 7 5 9 6 3 1 2
10 1
0 1 1 2 3 2 1...

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
9
7
8
9
1
7
1
9
6
8
6
9
9
4
9
7
9
3
8
9
32
39
38
35
38
88
996
98
39
25
38
38
39
6
1
7
7
9
7
6
6
1
4
9
6
4
9
5
9
7
8
9
5

result:

wrong answer 31st lines differ - expected: '23', found: '25'

Subtask #5:

score: 0

Wrong Answer

Dependency #3:

100%

Accepted

Test #29:

score: 0

Wrong Answer

time: 1ms

memory: 3712kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
53
10 5
0 1 2 3 4 5 6 7 8
9 7 6 8 5 3 4 1 2
9 7 6 8 5 4 3 1 2
9 7 6 8 5 3 4 1 2
9 6 8 7 5 3 4 2 1
9 6 8 7 5 4 3 2 1
10 5
0 1 2 3 4 5 6 7 8
9 8 7 6 5 4 3 2 1
9 8 7 5 4 6 3 1 2
9 8 7 5 6 4 3 2 1
9 8 7 5 6 4 3 1 2
9 8 7 6 4 5 3 2 1
10 5
0 1 2 3 4 5 6 7 8
8 9 7 5 6 4 2 3...

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

wrong answer 2nd lines differ - expected: '5', found: '0'

Subtask #6:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

Subtask #7:

score: 9

Accepted

Dependency #3:

100%

Accepted

Test #41:

score: 9

Accepted

time: 130ms

memory: 19208kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
2225
50 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
49 48 47 45 46 43 44 42 41 40 39 38 37 35 36 34 32 33 31 30 28 29 26 27 25 23 24 22 20 21 18 17 19 16 15 14 13 12 11 10 ...

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
37
42
32
34
38
33
30
42
43
29
28
29
42
37
42
30
30
30
29
30
35
34
29
33
28
37
41
29
35
35
32
40
45
36
30
31
38
42
42
34
37
23
33
43
36
37
36
20
33
30
38
41
38
38
32
39
42
31
34
30
32
41
40
30
23
40
40
45
41
37
40
36
42
33
27
34
35
36
32
31
34
37
36
39
46
42
42
39
25
...

result:

ok 2226 lines

Test #42:

score: 9

Accepted

time: 159ms

memory: 19228kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
2225
50 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
49 48 47 46 45 43 44 42 41 39 40 38 37 36 35 34 33 31 32 30 29 28 27 26 25 23 24 22 20 19 21 17 18 16 15 14 13 12 11 10 ...

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
42
41
40
36
17
35
12
39
29
41
41
34
20
33
42
36
20
36
41
25
18
37
29
15
17
11
6
39
35
7
34
37
42
40
39
44
1
3
29
39
42
20
35
42
18
39
31
26
26
35
28
7
4
42
13
24
39
19
27
40
26
14
1
39
19
44
1
6
13
38
12
6
39
38
29
40
47
38
36
43
42
43
41
20
41
6
21
44
43
37
14
44
25...

result:

ok 2226 lines

Test #43:

score: 9

Accepted

time: 153ms

memory: 19152kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
2225
50 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
49 47 48 46 45 43 44 42 41 40 39 37 38 36 34 35 33 32 31 30 28 29 27 26 25 23 24 21 22 20 19 18 16 17 15 14 13 12 11 10 ...

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
39
37
38
34
25
31
23
43
34
39
41
34
26
28
27
33
42
42
39
36
40
34
29
34
27
42
43
22
24
35
31
37
27
29
42
29
40
44
27
41
38
27
28
41
31
35
39
32
42
44
39
39
35
38
39
34
33
31
21
39
34
37
40
43
35
40
31
32
45
29
36
34
37
41
33
46
35
36
43
32
28
40
28
33
34
42
43
28
38
...

result:

ok 2226 lines

Test #44:

score: 9

Accepted

time: 145ms

memory: 19308kb

input:

txy4h26c1rm1uv8tr3eonahd67u8h56x
2225
50 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
49 48 47 45 46 43 44 42 41 40 38 39 35 37 36 33 34 32 30 28 29 31 27 26 25 24 23 21 22 20 19 18 17 16 15 13 14 12 11 10 ...

output:

7ckgnn4wyi495puj3ibqf81dqvapyv6b
35
24
38
37
15
33
30
3
35
42
3
44
40
28
41
29
13
38
15
21
29
36
15
40
25
22
42
7
31
39
40
37
26
39
8
25
22
44
28
36
3
13
5
7
13
17
42
45
36
41
36
10
15
40
7
5
40
26
44
27
34
23
40
19
31
21
36
1
33
33
26
25
26
39
37
24
46
37
14
36
28
8
42
23
38
35
41
44
31
42
22
10
36...

result:

ok 2226 lines

Subtask #8:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

Subtask #9:

score: 0

Skipped

Dependency #3:

100%

Accepted

Dependency #5:

Subtask #10:

score: 0

Skipped

Dependency #1:

100%

Accepted