QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #780248 | #2596. Even Forest | chuangshigame | RE | 1ms | 9828kb | C++14 | 874b | 2024-11-25 09:16:00 | 2024-11-25 09:16:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
const int inf=0x3f3f3f3f;
struct node{
int nxt,to;
}e[MAXN*2];
int head[MAXN],tot=0,n;
int s[MAXN],p[MAXN],o[MAXN];
void add(int x,int y){
e[++tot].nxt=head[x];
e[tot].to=y;
head[x]=tot;
}
void dfs(int x,int fa){
s[x]=0;p[x]=o[x]=inf;
int tt=0,cnt=0,mi=inf,mi2=inf;
for(int i=head[x];i;i=e[i].nxt){
int to=e[i].to;
if(to==fa)continue;
dfs(to,x);
s[x]+=min(s[to]+1,p[to]);
if(s[to]<o[to]+1)tt+=s[to],++cnt;
else{
tt+=o[to]+1;
int sp=s[to]-o[to]-1;
if(sp<mi)mi2=mi,mi=sp;
else if(sp<mi2)mi2=sp;
}
}
if(cnt==0)o[x]=tt+mi+mi2,p[x]=tt+mi;
else if(cnt==1)o[x]=tt+mi,p[x]=tt;
else o[x]=p[x]=tt;
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int x,y;cin>>x>>y;
add(x,y);add(y,x);
}
dfs(1,0);
cout<<min(s[1],o[1]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 9828kb
input:
4 1 2 2 3 3 4
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7640kb
input:
4 1 2 1 3 1 4
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7596kb
input:
6 1 2 2 3 4 2 4 5 6 4
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 7708kb
input:
1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 7596kb
input:
2 1 2
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 7788kb
input:
3 2 3 3 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 1ms
memory: 7792kb
input:
4 2 3 3 1 3 4
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 1ms
memory: 7592kb
input:
5 4 2 2 3 4 1 5 3
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 1ms
memory: 7632kb
input:
6 4 3 1 4 2 4 5 2 4 6
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 1ms
memory: 7712kb
input:
50 21 22 22 27 22 7 22 12 22 13 43 22 36 22 35 22 6 22 10 22 22 38 19 22 34 22 8 22 22 44 22 3 9 22 22 16 23 22 18 22 22 25 22 5 22 2 22 15 46 22 37 22 48 22 33 22 22 17 31 22 22 29 22 28 22 49 4 22 22 26 41 22 22 32 22 50 22 20 22 30 24 22 40 22 22 45 14 22 22 11 42 22 39 22 1 22 47 22
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: -100
Runtime Error
input:
1000000 851841 325834 455962 325834 135775 325834 525341 325834 265267 325834 868520 325834 834325 325834 867971 325834 325834 879726 325834 242607 325834 106951 122113 325834 325834 499633 727580 325834 325834 200171 325834 178877 325834 493841 957118 325834 325834 809324 325834 641895 325834 33338...