QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #275950 | #72. Mergers | DaiRuiChen007 | 0 | 48ms | 35204kb | C++20 | 995b | 2023-12-05 12:58:15 | 2023-12-05 12:58:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
vector <int> G[MAXN],C[MAXN];
int col[MAXN],dfn[MAXN],dcnt;
int cnt[MAXN],deg[MAXN];
inline void dfs0(int u,int fz) {
dfn[u]=++dcnt;
for(int v:G[u]) if(v^fz) dfs0(v,u);
}
inline void dfs1(int u,int fz) {
for(int v:G[u]) if(v^fz) dfs1(v,u),cnt[u]+=cnt[v];
}
inline void dfs2(int u,int fz,int c) {
for(int v:G[u]) if(v^fz) {
if(!cnt[v]) ++deg[c],++deg[v],dfs2(v,u,v);
else dfs2(v,u,c);
}
}
signed main() {
int n,k;
scanf("%d%d",&n,&k);
for(int i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
for(int i=1;i<=n;++i) scanf("%d",&col[i]),C[col[i]].push_back(i);
dfs0(1,0);
for(int i=1;i<=k;++i) {
cnt[*min_element(C[i].begin(),C[i].end(),[&](auto x,auto y){ return dfn[x]<dfn[y]; })]-=C[i].size();
for(int u:C[i]) ++cnt[u];
}
dfs1(1,0),dfs2(1,0,1);
int ans=0;
for(int i=1;i<=n;++i) if(!cnt[i]&°[i]==1) ++ans;
printf("%d\n",(ans+1)/2);
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: 0ms
memory: 27340kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 27160kb
input:
3 2 2 1 3 1 2 2 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 27116kb
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: 0ms
memory: 27096kb
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: 6ms
memory: 27100kb
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: 3ms
memory: 27104kb
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: -10
Wrong Answer
time: 0ms
memory: 27348kb
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:
1
result:
wrong answer 1st lines differ - expected: '0', found: '1'
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: 48ms
memory: 35204kb
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: 35ms
memory: 33396kb
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:
5439
result:
wrong answer 1st lines differ - expected: '4686', found: '5439'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%