QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #799952 | #8440. Toll Roads | cdx123456 | WA | 1ms | 3848kb | C++14 | 1.6kb | 2024-12-05 19:44:40 | 2024-12-05 19:44:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,K,s,t,sum,ansm,anss,anst,d[5010],d2[5010],g[5010];
vector<int> v[5010];
void dfs(int x,int fa){
d[x]=0;
d2[x]=-1e9;
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==fa) continue;
dfs(y,x);
if(d[y]+1>d[x]) d2[x]=d[x],d[x]=d[y]+1;
else if(d[y]+1>d2[x]) d2[x]=d[y]+1;
}
g[x]=max(d[x],d2[x]+d[x]);
}
bool dfs2(int x,int fa,int z,int max_d){
int cnt=0,k=0;
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==fa) continue;
if(g[y]>z || d[y]>max_d-1) cnt++,k=y;
}
if(cnt>1) return 0;
if(!cnt && g[x]<=z) return 1;
if(cnt==0){
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==fa) continue;
if(d[y]+1==d[x]) k=y;
}
}
int maxx=-1,maxx2=-1;
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==fa) continue;
if(y==k) continue;
if(d[y]>maxx) maxx2=maxx,maxx=d[y];
else if(d[y]>maxx2) maxx2=d[y];
}
if(maxx+maxx2+2>z) return 0;
if(dfs2(k,x,z,min(max_d,z-maxx-1))){
if(!t) t=k;
sum++;
return 1;
}
return 0;
}
bool check(int x){
int minn=1e9,mins=0,mint=0;
for(int i=1;i<=n;i++){
dfs(i,0);
s=i; t=sum=0;
if(dfs2(i,0,x,1e9) && sum<minn){
minn=sum;
mins=s;
mint=t;
}
}
if(minn>K) return 0;
ansm=minn;
anss=mins;
anst=mint;
return 1;
}
int main(){
int x,y,l=0,r=10000;
cin>>n>>K;
for(int i=1;i<n;i++){
cin>>x>>y;
v[x+1].push_back(y+1);
v[y+1].push_back(x+1);
}
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) r=mid-1;
else l=mid+1;
}
cout<<r+1<<endl;
cout<<ansm<<endl;
if(ansm) cout<<anss-1<<' '<<anst-1<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
8 3 0 2 0 5 2 3 5 1 4 5 5 6 6 7
output:
2 3 2 6
result:
ok n=8, K=3: cost=2, k=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
5 2 0 1 0 2 0 3 0 4
output:
2 0
result:
ok n=5, K=2: cost=2, k=0
Test #3:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
2 1 0 1
output:
0 1 0 1
result:
ok n=2, K=1: cost=0, k=1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
3 1 0 1 2 1
output:
1 1 0 1
result:
ok n=3, K=1: cost=1, k=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
3 1 0 2 1 2
output:
1 1 0 2
result:
ok n=3, K=1: cost=1, k=1
Test #6:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
3 2 0 2 1 2
output:
0 2 0 1
result:
ok n=3, K=2: cost=0, k=2
Test #7:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
4 1 0 3 0 1 3 2
output:
2 1 0 3
result:
ok n=4, K=1: cost=2, k=1
Test #8:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
4 2 0 3 0 1 3 2
output:
1 2 0 2
result:
ok n=4, K=2: cost=1, k=2
Test #9:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
4 3 0 3 0 1 3 2
output:
0 3 1 2
result:
ok n=4, K=3: cost=0, k=3
Test #10:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
4 1 0 1 0 2 0 3
output:
2 0
result:
ok n=4, K=1: cost=2, k=0
Test #11:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
4 2 0 1 0 2 0 3
output:
1 2 1 3
result:
ok n=4, K=2: cost=1, k=2
Test #12:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
4 3 0 1 0 2 0 3
output:
1 2 1 3
result:
ok n=4, K=3: cost=1, k=2
Test #13:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
6 3 0 1 0 2 0 3 2 4 3 5
output:
2 2 2 3
result:
ok n=6, K=3: cost=2, k=2
Test #14:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
6 3 0 1 0 2 0 3 2 4 2 5
output:
2 1 0 2
result:
ok n=6, K=3: cost=2, k=1
Test #15:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
8 5 0 1 1 2 2 3 0 4 4 5 5 6 0 7
output:
2 4 2 5
result:
ok n=8, K=5: cost=2, k=4
Test #16:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
2 1 0 1
output:
0 1 0 1
result:
ok n=2, K=1: cost=0, k=1
Test #17:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
3 1 2 1 0 2
output:
1 1 0 2
result:
ok n=3, K=1: cost=1, k=1
Test #18:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
3 1 0 2 0 1
output:
1 1 0 1
result:
ok n=3, K=1: cost=1, k=1
Test #19:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
3 2 1 0 1 2
output:
0 2 0 2
result:
ok n=3, K=2: cost=0, k=2
Test #20:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 2 0 1 0 2
output:
0 2 1 2
result:
ok n=3, K=2: cost=0, k=2
Test #21:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
4 1 2 1 2 0 1 3
output:
2 1 0 2
result:
ok n=4, K=1: cost=2, k=1
Test #22:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
4 1 2 0 0 3 1 0
output:
2 0
result:
ok n=4, K=1: cost=2, k=0
Test #23:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
4 2 3 0 1 2 2 3
output:
1 2 0 2
result:
ok n=4, K=2: cost=1, k=2
Test #24:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
4 2 1 0 0 3 0 2
output:
1 2 1 2
result:
ok n=4, K=2: cost=1, k=2
Test #25:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
4 3 3 0 3 2 2 1
output:
0 3 0 1
result:
ok n=4, K=3: cost=0, k=3
Test #26:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
4 3 1 0 3 0 2 0
output:
1 2 1 2
result:
ok n=4, K=3: cost=1, k=2
Test #27:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
10 3 3 0 8 1 9 5 0 4 0 1 7 5 6 8 2 8 5 8
output:
2 3 0 5
result:
ok n=10, K=3: cost=2, k=3
Test #28:
score: -100
Wrong Answer
time: 1ms
memory: 3768kb
input:
100 4 32 66 29 26 86 0 71 83 26 70 62 84 51 9 37 0 0 62 83 96 86 88 40 1 37 6 70 34 13 19 65 8 0 43 39 65 99 77 33 0 84 65 64 95 60 64 83 56 26 89 0 25 92 33 63 42 45 73 66 84 24 21 36 11 52 15 9 92 3 17 80 48 88 97 23 54 28 5 46 98 42 20 5 93 84 89 56 23 97 73 36 99 0 35 97 90 76 18 50 27 26 75 50 ...
output:
11 0
result:
wrong answer Diameter is promised to be 11, but it equals to 16