QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#357771#72. Mergerstuanlinh1230 64ms69396kbC++202.1kb2024-03-19 11:25:222024-03-19 11:25:23

Judging History

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

  • [2024-03-19 11:25:23]
  • 评测
  • 测评结果：0
  • 用时：64ms
  • 内存：69396kb
查看
  • [2024-03-19 11:25:22]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
 
const ll maxn=500005;
pll sp[20][maxn];
vector <pll> euler;
vector <ll> leaf, A[maxn];
ll P[maxn], col[maxn], lca[maxn], pa[maxn], dsu[maxn];
 
void dfs(ll u)
{
    lca[u]=sz(euler)+1, euler.pb({lca[u], u});
    for (ll v:A[u])
        if (v!=pa[u])
            pa[v]=u, dfs(v), euler.pb({lca[u], u});
    if (sz(A[u])==1) leaf.pb(u);
}
 
void initlca()
{
    ll n=sz(euler);
    for (ll i=0; i<n; i++)
        sp[0][i+1]=euler[i];
    for (ll i=1; i<20; i++)
        for (ll j=1; j+(1<<i)<=n+1; j++)
            sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
}
 
ll LCA(ll u, ll v)
{
    if (!u || !v) return u+v;
    ll l=lca[u], r=lca[v];
    if (l>r) swap(l, r);
    ll j=__lg(r-l+1);
    return min(sp[j][l], sp[j][r-(1<<j)+1]).se;
}
 
ll Find(ll i)
{
    if (dsu[i]<0) return i;
    return dsu[i]=Find(dsu[i]);
}
 
void Union(ll a, ll b)
{
    a=Find(a), b=Find(b);
    if (a==b) return;
    if (dsu[a]>dsu[b]) swap(a, b);
    P[a]=LCA(P[a], P[b]), dsu[a]+=dsu[b], dsu[b]=a;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, k; cin >> n >> k;
    for (ll i=1; i<n; i++)
    {
        ll u, v; cin >> u >> v;
        A[u].pb(v), A[v].pb(u);
    }
    dfs(1), initlca();
    for (ll i=1; i<=n; i++)
        cin >> col[i], P[col[i]]=LCA(P[col[i]], i), dsu[i]=-1;
    for (ll i=1; i<=n; i++)
        if (i!=P[col[i]])
            Union(col[i], col[pa[i]]);
    for (ll i=1; i<=n; i++) col[i]=Find(col[i]);
    for (ll i=1; i<=k; i++) P[i]=0;
    for (ll i=1; i<=n; i++)
        for (ll j:A[i])
            if (col[i]!=col[j])
            {
                if (P[col[i]]==0) P[col[i]]=col[j];
                else if (P[col[i]]!=col[j]) P[col[i]]=-1;
            }
    ll cnt=0;
    for (ll i=1; i<=k; i++)
        cnt+=P[i]>0;
    cout << (cnt+1)/2;
 
}
源文件, 语言: C++20

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 0ms
memory: 3692kb

input:

1 1
1

output:

0

result:

ok single line: '0'

Test #2:

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

input:

3 2
2 1
3 1
2
2
1

output:

1

result:

ok single line: '1'

Test #3:

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

input:

5 2
1 2
4 5
4 2
3 4
2
1
2
1
2

output:

0

result:

ok single line: '0'

Test #4:

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

input:

7 7
5 7
4 7
6 4
1 3
2 6
3 4
6
7
2
4
5
3
1

output:

2

result:

ok single line: '2'

Test #5:

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

input:

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

output:

0

result:

ok single line: '0'

Test #6:

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

input:

100 1
7 97
63 10
65 17
26 85
50 92
92 20
28 83
92 51
5 4
56 2
18 27
16 73
24 78
73 10
35 6
49 10
20 11
42 23
30 7
24 69
38 87
53 45
25 3
93 57
64 47
84 73
20 91
97 31
99 45
20 38
76 9
98 94
40 72
77 38
37 7
88 8
37 78
73 8
90 61
45 68
32 29
55 37
46 88
17 14
46 12
83 100
35 40
71 20
32 92
57 88
92 6...

output:

0

result:

ok single line: '0'

Test #7:

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

input:

100 7
53 48
26 44
28 93
71 74
7 58
76 79
8 89
44 71
80 6
31 67
76 33
90 24
55 1
62 41
95 35
44 68
29 24
18 56
60 85
71 42
71 1
50 78
12 46
67 50
86 50
71 18
17 51
49 13
63 41
2 25
19 93
74 43
74 39
51 43
2 3
61 49
40 61
48 84
99 62
98 43
80 92
58 76
22 43
58 10
50 14
5 26
75 55
19 51
45 38
3 8
23 52...

output:

0

result:

ok single line: '0'

Test #8:

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

input:

9 6
7 6
9 1
2 4
4 5
9 2
8 6
9 3
8 1
3
1
6
4
4
2
5
5
6

output:

1

result:

ok single line: '1'

Test #9:

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

input:

100 6
45 58
90 65
28 24
76 32
97 92
50 81
38 17
98 40
81 21
68 56
36 78
45 12
74 31
72 30
20 35
61 85
39 8
69 40
54 60
80 25
5 95
95 27
54 70
19 21
20 12
85 93
16 88
95 48
46 14
45 72
40 7
37 14
72 47
22 10
45 31
75 69
32 6
73 22
56 99
11 35
43 55
1 56
15 56
35 42
100 55
49 34
76 33
87 45
78 70
90 8...

output:

1

result:

ok single line: '1'

Test #10:

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

input:

99 6
44 2
26 24
42 67
94 92
77 97
79 58
50 75
2 12
52 39
30 60
97 94
32 62
12 3
68 8
48 85
18 40
94 37
42 10
7 37
24 12
40 84
41 71
87 49
37 51
22 55
10 9
16 14
52 85
20 86
41 65
69 10
12 55
79 80
50 80
37 16
94 63
93 2
95 31
46 53
65 83
47 9
84 92
4 23
11 98
24 28
54 66
12 72
58 49
40 64
73 39
30 4...

output:

1

result:

ok single line: '1'

Test #11:

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

input:

84 7
10 47
56 65
25 60
13 7
22 55
67 23
30 64
37 12
14 6
55 7
68 66
11 70
65 23
58 56
82 74
3 61
9 29
68 38
80 8
80 5
78 75
75 69
75 31
26 77
18 3
52 49
45 38
6 67
80 26
5 46
39 26
68 40
12 30
14 25
84 21
48 69
43 63
38 36
1 39
12 10
25 31
53 15
74 6
59 30
47 4
32 24
82 33
20 31
44 40
54 38
51 28
32...

output:

2

result:

ok single line: '2'

Test #12:

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

input:

7 7
3 4
7 1
2 1
7 5
5 6
4 6
3
7
2
1
5
4
6

output:

1

result:

ok single line: '1'

Test #13:

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

input:

8 7
6 3
8 1
7 8
1 5
6 7
2 4
3 2
5
4
4
1
3
6
7
2

output:

1

result:

ok single line: '1'

Test #14:

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

input:

100 7
76 43
72 84
5 41
9 38
93 79
11 12
88 52
97 59
69 73
48 49
61 44
17 82
53 55
30 33
87 64
80 37
58 99
53 42
22 36
31 62
88 35
95 75
68 67
29 41
18 84
34 5
1 58
26 14
80 6
1 24
6 36
44 77
55 38
99 9
56 47
45 47
31 13
46 71
61 20
81 3
75 97
39 3
50 60
74 17
66 34
57 95
7 11
8 23
98 28
21 10
22 64
...

output:

0

result:

ok single line: '0'

Test #15:

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

input:

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

output:

1

result:

ok single line: '1'

Test #16:

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

input:

99 6
67 79
71 88
94 20
63 45
56 61
38 83
59 50
21 88
9 51
93 15
54 87
51 36
29 18
24 96
10 25
16 47
5 92
56 45
30 15
22 25
34 1
37 18
38 19
43 76
78 17
61 72
22 64
32 44
52 54
84 3
53 98
42 60
7 89
9 6
92 43
32 66
12 87
4 16
77 10
47 97
33 58
17 35
75 41
23 41
65 26
11 80
7 74
12 79
72 33
97 31
20 5...

output:

1

result:

ok single line: '1'

Test #17:

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

input:

100 6
14 86
25 42
67 97
24 34
12 18
97 31
93 69
1 56
71 100
82 43
55 69
12 33
79 39
88 73
60 62
28 35
21 11
41 89
17 29
63 61
59 75
54 96
13 89
47 58
43 45
50 56
91 74
11 7
20 40
71 94
73 6
38 64
35 23
22 5
93 38
90 54
10 57
23 36
3 22
99 72
74 66
27 18
55 30
9 92
50 78
85 87
26 68
28 60
8 46
44 14
...

output:

1

result:

ok single line: '1'

Test #18:

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

input:

84 7
17 69
82 35
23 65
17 61
57 68
19 40
54 77
10 9
26 11
25 81
19 39
41 71
20 57
28 60
31 83
3 30
31 64
22 52
37 29
38 7
58 59
42 66
66 46
20 25
11 43
71 48
56 51
44 53
76 62
67 21
1 22
46 8
49 33
72 47
38 33
7 70
18 36
43 59
15 9
32 69
30 12
5 4
15 14
8 21
55 39
50 48
41 16
45 4
63 38
24 11
36 12
...

output:

2

result:

ok single line: '2'

Test #19:

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

input:

7 7
7 3
6 3
1 3
4 3
5 3
3 2
7
4
5
6
2
3
1

output:

3

result:

ok single line: '3'

Test #20:

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

input:

15 7
7 9
4 7
7 2
14 7
7 6
7 12
7 3
11 7
7 15
5 7
7 13
8 7
10 7
7 1
7
6
3
4
4
1
3
7
6
3
5
7
2
2
1

output:

1

result:

ok single line: '1'

Test #21:

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

input:

100 7
56 87
56 74
39 56
83 56
99 56
28 56
56 3
56 62
48 56
56 20
24 56
56 17
30 56
11 56
56 40
73 56
56 61
56 6
56 16
2 56
56 94
19 56
56 85
56 70
56 68
57 56
56 75
53 56
56 1
56 59
71 56
47 56
55 56
56 31
80 56
93 56
56 66
14 56
56 76
56 97
56 89
35 56
56 49
12 56
56 82
58 56
100 56
95 56
9 56
56 4...

output:

0

result:

ok single line: '0'

Test #22:

score: -10
Wrong Answer
time: 0ms
memory: 3652kb

input:

8 7
6 8
8 7
4 1
8 2
8 3
8 5
4 8
1
6
5
2
7
4
1
3

output:

3

result:

wrong answer 1st lines differ - expected: '2', found: '3'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #66:

score: 22
Accepted
time: 46ms
memory: 69396kb

input:

100000 100000
14957 4585
67467 70858
61843 47396
50630 17382
61027 39858
94990 21698
10240 22940
23505 67581
91432 14182
22040 40125
24556 60351
75822 41519
82801 23601
90653 29138
85096 34582
99587 59109
8932 45189
18235 36632
43160 14939
67600 76675
60175 65542
99294 53955
46429 66931
16822 48854
...

output:

25042

result:

ok single line: '25042'

Test #67:

score: -22
Wrong Answer
time: 64ms
memory: 68844kb

input:

100000 50000
3065 28396
57666 99424
91431 92279
85107 9397
40557 2609
33754 76986
41982 13262
29268 57814
57080 70949
46008 55628
16881 69517
7925 97656
11194 27261
1023 44957
63053 94265
10347 36227
57858 50853
6707 37237
14023 64077
97278 89836
45448 37054
47530 12666
1789 54939
97196 38225
46942 ...

output:

4870

result:

wrong answer 1st lines differ - expected: '4686', found: '4870'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

伺服器時間: 2025-01-20 12:09:00 | 開源專案