QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #607058 | #72. Mergers | SimonLJK | 0 | 18ms | 18272kb | C++14 | 945b | 2024-10-03 13:48:14 | 2024-10-03 13:48:15 |
Judging History
answer
// LUOGU_RID: 179653037
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e6+999;
int n,c[N];
ull val[N],cval[N];
mt19937_64 ran(1567184113);
struct edge{
int v,nxt;
}edg[N*2];
int cntedge,hd[N];
void add(int u,int v){
edg[++cntedge]=(edge){v,hd[u]};
hd[u]=cntedge;
}
int ans,b[N];
void dfs(int u,int fa){
int v;
for(int i=hd[u];i;i=edg[i].nxt){
v=edg[i].v;
if(v==fa) continue;
dfs(v,u);
val[u]^=val[v];
b[u]+=(b[v]>0);
}
if(!b[u]&&!val[u]&&u!=1){
ans++;
b[u]=1;
}
return;
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
int u,v,k;
cin>>n>>k;
for(int i=1;i<n;i++){
cin>>u>>v;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++){
cin>>c[i];
val[i]=ran();
cval[c[i]]^=val[i];
}
for(int i=1;i<=n;i++){
val[i]^=cval[c[i]];
cval[c[i]]=0;
}
dfs(1,0);
if(b[1]==1) ans++;
cout<<(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: 1ms
memory: 9656kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #2:
score: 10
Accepted
time: 0ms
memory: 9800kb
input:
3 2 2 1 3 1 2 2 1
output:
1
result:
ok single line: '1'
Test #3:
score: 10
Accepted
time: 1ms
memory: 9788kb
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: 10
Accepted
time: 1ms
memory: 9672kb
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: 10
Accepted
time: 1ms
memory: 9716kb
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: 10
Accepted
time: 1ms
memory: 9804kb
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
Accepted
time: 0ms
memory: 9768kb
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: 10
Accepted
time: 2ms
memory: 9768kb
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: 10
Accepted
time: 1ms
memory: 9780kb
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
Wrong Answer
time: 1ms
memory: 9764kb
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:
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: 16ms
memory: 17396kb
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: 0
Wrong Answer
time: 18ms
memory: 18272kb
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:
4687
result:
wrong answer 1st lines differ - expected: '4686', found: '4687'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%