QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #95705 | #72. Mergers | eyiigjkn | 0 | 63ms | 38716kb | C++14 | 950b | 2023-04-11 14:55:06 | 2023-04-11 14:55:07 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
int ans=0,cnt[500010],cnt2[500010],cnt3[500010],dep[500010];
vector<int> G[500010],vec[500010];
void dfs1(int u,int fa)
{
for(int v:G[u])
{
if(v==fa) continue;
dep[v]=dep[u]+1;
dfs1(v,u);
}
}
void dfs2(int u,int fa)
{
for(int v:G[u])
{
if(v==fa) continue;
dfs2(v,u);
cnt[u]+=cnt[v];
cnt2[u]+=cnt2[v]+(!cnt[v]);
cnt3[u]+=!cnt[v];
ans+=(!cnt[v] && !cnt2[v]);
}
}
int main()
{
int n,m,u,v;
cin>>n>>m;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(1,0);
for(int i=1;i<=n;i++) scanf("%d",&u),vec[u].push_back(i);
for(int i=1;i<=m;i++)
{
int mn=0;
for(int u:vec[i])
{
cnt[u]++;
if(!mn || dep[u]<dep[mn]) mn=u;
}
cnt[mn]-=vec[i].size();
}
dfs2(1,0);
for(int i=1;i<=n;i++) ans+=(cnt2[i]==cnt2[1] && cnt3[i]==1);
ans=(ans+1)/2;
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 2ms
memory: 30948kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 8ms
memory: 32428kb
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: 31548kb
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: 6ms
memory: 32372kb
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: 4ms
memory: 32184kb
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: 12ms
memory: 32532kb
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: 6ms
memory: 32728kb
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: 3ms
memory: 31116kb
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: 31572kb
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: 2ms
memory: 30924kb
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: 32876kb
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: 5ms
memory: 31716kb
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: 8ms
memory: 31888kb
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: 32476kb
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: 0ms
memory: 32760kb
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: 31492kb
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: 4ms
memory: 32804kb
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: 7ms
memory: 32192kb
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: 4ms
memory: 31024kb
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: 3ms
memory: 33100kb
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: 7ms
memory: 32816kb
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: 0
Accepted
time: 3ms
memory: 32292kb
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:
2
result:
ok single line: '2'
Test #23:
score: -10
Wrong Answer
time: 3ms
memory: 32572kb
input:
10 7 1 5 10 9 7 9 2 10 3 2 9 8 6 8 4 10 5 8 6 1 7 2 5 4 6 2 3 1
output:
2
result:
wrong answer 1st lines differ - expected: '1', found: '2'
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: 56ms
memory: 38716kb
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: 63ms
memory: 37832kb
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:
5305
result:
wrong answer 1st lines differ - expected: '4686', found: '5305'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%