QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #780222 | #2596. Even Forest | niumachaoren | WA | 200ms | 96984kb | C++14 | 1.0kb | 2024-11-25 08:53:37 | 2024-11-25 08:53:37 |
Judging History
answer
#include<bits/stdc++.h>
inline void read(int &x){
x=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
}
using namespace std;
const int maxn=1e6+10;
int n,rt,dep[maxn],dp[maxn][2];
vector<int>e[maxn<<1];
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
int siz=0;
for(int v:e[u]){
if(v==fa)continue;
siz++;
dfs(v,u);
dp[u][0]+=min(dp[v][0],dp[v][1]+1);
dp[u][1]+=min(dp[v][1],dp[v][0]+1);
}
if(!siz){
dp[u][dep[u]&1]=1;
}
}
int main(){
srand((unsigned)time(NULL));
read(n);
for(int i=1;i<n;i++){
int u,v;
read(u),read(v);
e[u].push_back(v),e[v].push_back(u);
}
int cnt=0;
for(int i=1;i<=n;i++){
if(e[i].size()==1)cnt++;
}
if(cnt==2){
cout<<((n&1)^1)<<'\n';
return 0;
}
rt=rand()%n+1;
dfs(rt,0);
int ans=min(dp[rt][0],dp[rt][1]);
memset(dp,0,sizeof(dp));
memset(dep,0,sizeof(dep));
rt=rand()%n+1;
dfs(rt,0);
ans=max(ans,min(dp[rt][0],dp[rt][1]));
cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 51700kb
input:
4 1 2 2 3 3 4
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 4ms
memory: 62392kb
input:
4 1 2 1 3 1 4
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 3ms
memory: 62220kb
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: 0ms
memory: 62256kb
input:
1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 8ms
memory: 51792kb
input:
2 1 2
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 6ms
memory: 51044kb
input:
3 2 3 3 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 0ms
memory: 62192kb
input:
4 2 3 3 1 3 4
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 4ms
memory: 50632kb
input:
5 4 2 2 3 4 1 5 3
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 4ms
memory: 62196kb
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: 4ms
memory: 62408kb
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: 0
Accepted
time: 200ms
memory: 96984kb
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...
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 3ms
memory: 51284kb
input:
3 2 1 2 3
output:
0
result:
ok 1 number(s): "0"
Test #13:
score: 0
Accepted
time: 0ms
memory: 51184kb
input:
4 4 3 1 4 1 2
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 3ms
memory: 50544kb
input:
5 1 4 2 4 3 2 3 5
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 9ms
memory: 50672kb
input:
6 3 5 3 6 1 6 1 4 4 2
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 4ms
memory: 50844kb
input:
7 1 2 3 2 6 3 6 7 7 4 4 5
output:
0
result:
ok 1 number(s): "0"
Test #17:
score: 0
Accepted
time: 3ms
memory: 50692kb
input:
8 6 2 1 2 8 1 5 8 5 7 7 3 4 3
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: 0
Accepted
time: 9ms
memory: 50480kb
input:
20 6 1 6 15 9 15 18 9 18 17 17 7 8 7 3 8 19 3 2 19 13 2 13 11 12 11 12 14 4 14 4 5 20 5 16 20 16 10
output:
1
result:
ok 1 number(s): "1"
Test #19:
score: 0
Accepted
time: 7ms
memory: 50540kb
input:
42 33 30 17 33 17 7 29 7 15 29 15 23 23 1 10 1 10 31 4 31 12 4 12 34 28 34 28 41 41 11 32 11 32 24 13 24 13 19 26 19 16 26 35 16 35 27 37 27 37 3 3 20 8 20 39 8 6 39 6 42 14 42 14 38 38 9 25 9 18 25 18 5 36 5 36 40 40 21 21 2 22 2
output:
1
result:
ok 1 number(s): "1"
Test #20:
score: 0
Accepted
time: 3ms
memory: 62348kb
input:
27 19 14 6 19 16 19 19 7 19 4 21 19 26 4 26 15 4 5 5 1 10 26 13 26 17 7 3 4 23 13 21 25 2 25 2 12 10 9 20 17 24 16 21 27 22 13 8 16 18 7 11 24
output:
6
result:
ok 1 number(s): "6"
Test #21:
score: 0
Accepted
time: 3ms
memory: 62312kb
input:
2007 1852 380 380 1300 1437 380 380 1789 380 876 380 1427 1295 1852 380 1549 782 1549 205 380 1789 446 1300 1113 380 417 446 1357 1295 242 446 1758 579 417 562 242 1086 1437 1584 876 579 1981 1873 1789 1918 1789 376 1437 1113 1564 30 1113 1357 1197 221 446 1300 128 386 579 1918 1126 479 1549 1026 15...
output:
326
result:
ok 1 number(s): "326"
Test #22:
score: 0
Accepted
time: 4ms
memory: 62408kb
input:
582 422 513 284 422 571 422 148 422 422 315 420 422 422 143 92 422 422 94 177 422 67 422 112 422 422 424 343 422 219 422 422 263 422 131 19 422 422 322 422 257 455 422 371 422 422 580 431 422 422 160 123 422 531 422 422 474 422 189 471 422 422 168 77 422 438 422 232 422 422 336 239 422 422 467 186 4...
output:
65
result:
ok 1 number(s): "65"
Test #23:
score: 0
Accepted
time: 3ms
memory: 62364kb
input:
2007 1191 1713 1191 1921 1191 63 1191 272 1191 774 1191 1116 656 1191 1191 154 1872 1191 453 1191 1191 411 1599 1191 1420 1191 810 1191 1191 1470 1191 1017 457 1191 1191 987 101 1191 1794 1191 1191 1404 134 1191 1080 1191 918 1191 955 1191 1191 1124 1191 1042 1191 1369 1191 51 88 1191 1315 1191 1191...
output:
7
result:
ok 1 number(s): "7"
Test #24:
score: 0
Accepted
time: 4ms
memory: 62248kb
input:
50 43 40 28 43 32 43 50 43 29 43 43 45 43 49 43 2 43 5 43 23 7 43 43 31 43 35 43 38 4 43 16 43 43 8 20 43 20 33 43 13 39 13 9 43 17 9 18 43 18 37 43 42 42 25 43 14 41 14 43 10 27 10 3 43 48 3 43 26 19 26 43 47 24 47 21 43 6 21 11 43 11 34 43 30 22 30 43 44 46 44 43 1 1 12 43 36 36 15
output:
16
result:
ok 1 number(s): "16"
Test #25:
score: -100
Wrong Answer
time: 4ms
memory: 62276kb
input:
505 4 447 447 441 120 447 238 447 447 108 447 256 38 447 447 464 77 447 292 447 447 276 130 447 237 447 478 447 100 447 414 447 245 447 447 195 295 447 349 447 447 119 173 447 203 447 501 447 192 447 447 421 447 223 447 282 470 447 447 174 128 447 447 422 236 447 104 447 91 447 447 16 447 270 447 42...
output:
167
result:
wrong answer 1st numbers differ - expected: '168', found: '167'