QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423878#8704. 排队Williamxzh27 74ms9980kbC++231.2kb2024-05-28 18:41:532024-05-28 18:41:53

Judging History

This is the latest submission verdict.

  • [2024-05-28 18:41:53]
  • Judged
  • Verdict: 27
  • Time: 74ms
  • Memory: 9980kb
Show
  • [2024-05-28 18:41:53]
  • Submitted

answer

#include <bits/stdc++.h>
#define il inline
using namespace std;
il int read(){
    int x=0,c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-48,c=getchar();
    return x;
}
const int N=5e5+5;
int sid,T,n,m,fa[N],siz[N];
vector<int> e[N];
il void adde(int x,int y){e[x].push_back(y);}
il void add(int x,int v){
    while(x!=-1) siz[x]+=v,x=fa[x];
}
il bool cmp(int x,int y){return x>y;}
il int get(int x){
    int ret=1,y=fa[x];
    while(x){
        y=fa[x];sort(e[y].begin(),e[y].end(),cmp);
        for(int z:e[y]) if(z!=x) ret+=siz[z];else break;
        x=y,ret+=(y>0);
    }
    return ret;
}
il void del(int x){
    int y=fa[x];
    for(int i=0;i<e[y].size();++i)
        if(e[y][i]==x){e[y].erase(e[y].begin()+i);return ;}
}
int opt,x,y,z,u,v,w;
int main(){
    scanf("%d%d",&sid,&T);fa[0]=-1,siz[0]=1;
    for(int i=1;i<=T;++i){
        opt=read();
        if(opt==1) x=read(),y=++n,fa[y]=x,adde(x,y),add(y,1);
        if(opt==2){
            x=read(),u=read();
            add(fa[x],-siz[x]),del(x);
            adde(u,x),fa[x]=u,add(u,siz[x]);
        }
        if(opt==3){
            x=read();
            printf("%d\n",get(x));
        }
    }

    return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 2ms
memory: 7984kb

input:

0 8
1 0
1 1
1 2
3 2
2 2 0
3 1
3 2
3 3

output:

2
3
1
2

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 7856kb

input:

0 485
1 0
2 1 0
2 1 0
3 1
3 1
1 0
1 1
3 3
2 3 2
2 2 1
2 2 1
2 2 0
3 1
3 1
3 1
1 0
2 3 0
1 2
3 3
1 3
2 3 2
1 1
2 2 0
1 3
2 3 0
2 1 0
1 1
2 8 6
2 3 0
3 3
2 4 1
1 4
3 2
1 0
1 5
1 4
2 3 2
2 7 4
3 5
1 7
1 8
2 7 5
3 14
3 2
2 6 2
3 13
1 0
3 11
1 13
3 1
3 4
1 4
2 15 0
2 15 9
2 17 16
3 13
1 17
2 17 12
3 3
3 ...

output:

1
1
3
3
3
3
2
2
4
3
6
2
14
2
12
14
17
12
5
12
18
15
13
7
23
29
19
13
22
13
19
36
4
15
38
35
30
31
43
2
32
11
53
15
40
3
36
39
16
25
30
24
7
10
14
38
12
38
40
35
10
19
30
15
31
8
15
69
2
24
3
30
44
57
57
38
41
37
40
50
40
17
65
83
49
56
74
17
40
82
39
71
92
26
37
76
8
34
14
63
37
43
13
46
37
92
19
69...

result:

ok 153 lines

Test #3:

score: 0
Accepted
time: 2ms
memory: 7984kb

input:

0 475
1 0
2 1 0
2 1 0
3 1
2 1 0
3 1
3 1
3 1
3 1
3 1
2 1 0
1 1
1 1
1 3
3 1
1 2
2 3 2
1 0
3 2
3 2
2 6 3
1 5
3 7
1 5
1 5
1 1
1 5
3 9
1 7
3 6
3 5
3 1
2 10 2
1 3
1 10
1 13
3 8
2 5 0
2 7 0
2 11 6
1 7
1 15
2 11 2
2 3 0
1 5
3 11
2 14 7
2 7 5
2 1 0
3 16
3 14
1 16
2 13 2
3 10
2 12 7
2 1 0
1 2
3 19
1 12
3 19
1...

output:

1
1
1
1
1
1
1
3
3
4
6
11
4
1
8
16
6
7
19
7
7
5
28
10
28
22
9
31
3
21
23
31
26
9
30
5
39
40
45
48
1
28
54
47
4
48
37
50
26
5
22
41
12
1
63
46
32
62
43
28
45
23
37
1
13
20
64
10
48
7
41
13
10
54
16
10
66
7
65
1
76
35
74
14
56
16
28
68
76
10
80
12
4
25
4
13
44
69
76
4
21
15
4
49
90
39
87
42
90
73
43
94...

result:

ok 159 lines

Test #4:

score: 0
Accepted
time: 1ms
memory: 7904kb

input:

0 473
1 0
3 1
2 1 0
3 1
2 1 0
1 0
1 1
1 1
2 1 0
3 4
1 3
1 1
1 2
3 4
1 6
2 6 1
3 2
1 1
2 4 0
3 6
2 8 5
2 6 2
2 3 0
2 7 2
1 3
2 4 2
3 3
3 3
2 1 0
2 3 2
1 6
1 6
3 7
3 1
2 2 0
3 4
3 6
1 2
3 5
3 8
1 9
2 4 2
1 5
1 6
2 3 0
3 16
1 4
2 8 3
3 15
3 6
3 1
1 7
3 11
1 6
1 10
1 20
3 10
1 20
1 22
3 19
3 8
1 11
3 2
...

output:

1
1
3
5
1
6
1
1
2
11
6
3
10
11
10
5
9
15
13
2
15
7
10
6
29
17
10
26
6
3
30
18
31
11
17
7
22
24
17
30
19
26
14
40
43
6
14
37
43
46
9
44
45
12
7
24
23
18
10
39
56
3
50
18
1
50
69
69
37
44
20
30
2
17
41
61
60
39
25
27
66
8
16
81
43
54
10
79
59
56
63
10
11
26
75
42
10
46
6
12
77
69
36
6
99
67
79
1
83
47...

result:

ok 145 lines

Subtask #2:

score: 0
Time Limit Exceeded

Test #5:

score: 0
Time Limit Exceeded

input:

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

output:

1
1
1
1
1
1
3
3
1
3
4
5
7
4
1
4
3
7
14
2
7
3
18
17
11
4
13
2
2
18
21
12
17
3
3
22
22
6
5
20
5
17
22
27
18
23
31
4
1
19
21
12
22
34
33
5
22
40
40
8
14
42
35
9
40
24
18
13
36
8
25
49
32
34
47
14
47
19
38
10
14
31
40
17
20
45
46
1
35
1
43
9
47
33
56
2
8
19
41
21
18
50
22
61
27
2
2
6
4
58
62
35
61
59
10...

result:

Subtask #3:

score: 0
Time Limit Exceeded

Test #20:

score: 0
Time Limit Exceeded

input:

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

output:

2
2
1
1
4
2
4
1
1
8
5
10
5
10
8
5
8
9
8
11
1
2
1
8
6
11
9
3
2
4
4
9
3
15
13
12
4
9
4
12
10
6
2
4
10
9
16
2
15
13
13
7
3
3
11
21
7
5
4
2
10
5
15
20
6
17
12
5
24
4
15
13
7
10
17
6
19
9
19
19
12
3
18
16
21
19
26
12
25
21
19
10
14
24
8
8
14
16
32
8
14
33
30
14
4
1
20
21
37
22
25
7
18
27
28
35
37
18
33
4...

result:

Subtask #4:

score: 23
Accepted

Test #35:

score: 23
Accepted
time: 74ms
memory: 9868kb

input:

3 299743
1 0
1 1
3 1
1 2
3 2
1 0
3 3
3 2
3 1
3 2
2 2 1
3 3
3 3
3 4
3 1
3 2
3 2
2 1 0
3 2
3 1
3 1
1 0
3 2
1 2
1 1
3 2
2 5 2
1 6
1 0
2 5 2
1 7
3 8
3 5
3 5
2 7 5
2 9 4
3 5
3 8
2 6 2
2 3 0
2 2 0
1 1
2 3 1
1 8
2 7 0
3 3
1 12
2 13 9
1 5
2 2 1
2 14 13
1 12
2 1 0
2 12 10
2 15 12
1 0
1 6
3 6
2 3 2
2 17 6
3 4...

output:

1
2
4
3
2
3
4
4
1
2
3
3
3
2
2
4
5
8
9
9
7
6
12
14
6
18
11
4
4
18
7
14
5
11
11
25
10
13
14
5
17
19
12
19
10
19
34
32
3
41
19
44
6
2
22
8
34
36
18
16
10
37
24
37
3
2
55
33
28
43
8
44
61
9
18
28
31
64
45
54
18
51
7
71
61
6
59
19
37
4
47
83
81
20
71
24
24
66
93
33
48
59
23
35
60
43
47
79
44
40
22
84
17
...

result:

ok 99743 lines

Test #36:

score: 0
Accepted
time: 70ms
memory: 9968kb

input:

3 299432
1 0
3 1
1 1
2 1 0
1 2
2 3 1
1 2
1 3
2 4 3
1 5
2 2 0
3 6
2 1 0
1 4
2 4 1
3 2
1 3
3 3
3 5
2 7 0
1 6
2 9 8
3 1
3 8
3 8
1 4
2 10 7
1 2
1 1
2 1 0
1 11
3 5
3 4
1 0
3 11
1 11
2 10 3
3 13
3 10
1 1
3 11
1 7
1 8
3 11
3 3
3 16
3 1
3 13
3 2
2 8 4
1 7
2 17 6
3 1
3 3
3 5
3 2
1 2
1 13
3 15
2 5 2
1 5
3 13
...

output:

1
5
1
5
7
3
6
6
12
8
5
6
11
4
5
12
9
8
7
4
8
15
17
4
7
8
18
23
3
4
1
15
1
16
26
21
13
16
23
29
20
25
26
24
26
38
42
43
18
21
37
8
29
42
50
9
6
54
19
24
29
12
14
21
6
44
30
27
25
39
21
11
39
38
43
29
8
28
6
18
52
29
11
17
23
13
13
35
7
35
71
16
56
19
38
34
54
7
73
28
58
1
22
27
51
53
23
95
57
41
96
9...

result:

ok 99750 lines

Test #37:

score: 0
Accepted
time: 74ms
memory: 9980kb

input:

3 299115
1 0
3 1
3 1
2 1 0
1 1
2 2 0
3 1
2 2 0
3 1
3 2
2 1 0
2 2 1
2 1 0
1 2
3 1
2 1 0
2 1 0
1 2
3 3
1 0
2 1 0
1 3
2 2 0
3 2
2 4 1
3 3
2 6 5
3 4
1 6
1 1
3 3
1 5
2 9 7
1 1
3 10
2 10 8
3 10
3 9
2 5 4
1 4
3 8
2 10 3
3 10
1 6
1 12
3 13
1 9
3 2
2 11 8
1 8
2 5 4
2 15 8
1 2
1 11
3 5
3 9
1 16
3 11
3 12
1 3
...

output:

1
1
2
2
1
1
4
2
3
6
5
8
9
4
4
3
11
1
11
16
9
14
9
9
9
15
22
5
5
13
22
10
18
15
27
6
7
35
14
22
28
38
3
3
4
16
11
8
26
15
35
30
27
21
37
19
16
56
4
32
54
32
18
19
13
22
44
28
62
22
2
77
28
79
60
44
78
46
34
45
5
35
8
61
16
59
60
1
76
11
19
86
11
51
59
73
23
104
96
35
88
66
9
10
85
23
83
85
97
81
97
1...

result:

ok 99683 lines

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

Server Time: 2025-02-08 12:25:21 | OpenSource Project