QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#104099 | #392. Patrol | fzj2007 | 53.333333 | 17ms | 7560kb | C++14 | 2.5kb | 2023-05-08 16:42:19 | 2023-05-08 16:42:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>inline bool read(T &x){
x=0;
char ch=getchar();
bool flag=0,ret=0;
while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
x=flag?-x:x;
return ret;
}
template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
return read(a)&&read(args...);
}
template<typename T>void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
prt(x);
}
template<typename T>inline void put(char ch,T x){
if(x<0) putchar('-'),x=-x;
prt(x);
putchar(ch);
}
template<typename T,typename ...Args>inline void put(T a,Args ...args){
put(a);
put(args...);
}
template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
put(ch,a);
put(ch,args...);
}
inline void put(string s){
for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
}
inline void put(const char* s){
for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
}
}
using namespace IO;
#define N 100005
#define inf 2000000
struct edge{
int v,nxt,w;
}e[N<<1];
int head[N],cnt=1,f[N],ans,res;
inline void add(int u,int v){
e[++cnt]=(edge){v,head[u],1},head[u]=cnt;
}
inline void dfs(int x,int fa){
int mx1=-inf,mx2=-inf;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa) continue;
dfs(v,x);
if(f[v]+e[i].w>mx1) mx2=mx1,mx1=f[v]+e[i].w;
else if(f[v]+e[i].w>mx2) mx2=f[v]+e[i].w;
}
ans=max(ans,mx1+mx2),f[x]=max(mx1,0),ans=max(ans,f[x]);
}
inline void upd(int x,int fa){
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa) continue;
if(f[x]==f[v]+e[i].w) return e[i].w=e[i^1].w=-1,upd(v,x),void();
}
}
inline void update(int x,int fa){
int mx1=-inf,mx2=-inf,ps1=-1,ps2=-1;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa) continue;
update(v,x);
if(f[v]+e[i].w>mx1) mx2=mx1,ps2=ps1,mx1=f[v]+e[i].w,ps1=v;
else if(f[v]+e[i].w>mx2) mx2=f[v]+e[i].w,ps2=v;
}
if(mx1+mx2==ans)
return upd(e[ps1].v,x),upd(e[ps2].v,x),e[ps1].w=e[ps1^1].w=e[ps2].w=e[ps2^1].w=-1,void();
if(mx1==ans) return upd(e[ps1].v,x),e[ps1].w=e[ps1^1].w=-1,void();
}
int n,m;
int main(){
read(n,m),ans=0;
for(int i=1,u,v;i<n;i++) read(u,v),add(u,v),add(v,u);
dfs(1,0);
if(m==1) return put('\n',n+n-2+1-ans),0;
update(1,0),res=ans,ans=0,dfs(1,0);
put('\n',n+n-2+2-ans-res);
return 0;
}
詳細信息
Test #1:
score: 3.33333
Accepted
time: 2ms
memory: 3324kb
input:
10 1 2 1 3 1 4 1 5 2 6 5 7 1 8 2 9 2 10 9
output:
15
result:
ok single line: '15'
Test #2:
score: 3.33333
Accepted
time: 2ms
memory: 3356kb
input:
200 1 2 1 3 2 4 3 5 1 6 5 7 6 8 6 9 7 10 4 11 5 12 6 13 2 14 1 15 1 16 8 17 5 18 11 19 1 20 17 21 20 22 14 23 22 24 5 25 1 26 12 27 24 28 24 29 5 30 18 31 27 32 16 33 32 34 21 35 29 36 2 37 1 38 1 39 16 40 7 41 25 42 35 43 17 44 37 45 7 46 15 47 31 48 28 49 7 50 4 51 31 52 26 53 42 54 9 55 14 56 35 ...
output:
385
result:
ok single line: '385'
Test #3:
score: 3.33333
Accepted
time: 2ms
memory: 3540kb
input:
1000 1 2 1 3 2 4 2 5 3 6 1 7 1 8 7 9 3 10 8 11 10 12 10 13 12 14 6 15 8 16 13 17 9 18 8 19 10 20 10 21 11 22 14 23 20 24 21 25 14 26 23 27 20 28 22 29 27 30 27 31 20 32 25 33 23 34 26 35 26 36 26 37 35 38 29 39 34 40 34 41 39 42 40 43 41 44 39 45 44 46 37 47 39 48 43 49 40 50 49 51 46 52 50 53 44 54...
output:
1831
result:
ok single line: '1831'
Test #4:
score: 3.33333
Accepted
time: 0ms
memory: 3484kb
input:
5000 1 2 1 3 2 4 3 5 1 6 5 7 6 8 4 9 4 10 1 11 1 12 8 13 10 14 12 15 1 16 3 17 7 18 12 19 6 20 3 21 12 22 15 23 13 24 23 25 8 26 9 27 19 28 23 29 3 30 23 31 17 32 28 33 27 34 25 35 22 36 32 37 6 38 35 39 14 40 36 41 36 42 37 43 35 44 28 45 12 46 1 47 17 48 7 49 11 50 14 51 43 52 43 53 32 54 42 55 51...
output:
9965
result:
ok single line: '9965'
Test #5:
score: 3.33333
Accepted
time: 4ms
memory: 3980kb
input:
20000 1 2 1 3 1 4 3 5 4 6 1 7 3 8 4 9 3 10 4 11 9 12 8 13 5 14 7 15 4 16 9 17 8 18 14 19 13 20 15 21 18 22 13 23 1 24 20 25 4 26 8 27 14 28 21 29 1 30 11 31 22 32 21 33 13 34 28 35 18 36 34 37 14 38 24 39 7 40 7 41 3 42 12 43 3 44 8 45 41 46 8 47 15 48 38 49 11 50 25 51 4 52 14 53 17 54 28 55 44 56 ...
output:
39961
result:
ok single line: '39961'
Test #6:
score: 3.33333
Accepted
time: 17ms
memory: 6400kb
input:
100000 1 2 1 3 2 4 3 5 4 6 4 7 3 8 7 9 6 10 7 11 1 12 6 13 7 14 5 15 5 16 1 17 12 18 17 19 10 20 6 21 7 22 8 23 4 24 13 25 4 26 10 27 5 28 4 29 15 30 1 31 13 32 4 33 27 34 11 35 22 36 24 37 36 38 29 39 13 40 25 41 26 42 12 43 13 44 7 45 14 46 39 47 18 48 38 49 29 50 5 51 12 52 14 53 49 54 25 55 8 56...
output:
199955
result:
ok single line: '199955'
Test #7:
score: 3.33333
Accepted
time: 0ms
memory: 3700kb
input:
10000 1 2 1 3 1 4 3 5 3 6 3 7 5 8 2 9 2 10 3 11 4 12 1 13 5 14 8 15 6 16 13 17 15 18 13 19 8 20 11 21 11 22 17 23 13 24 14 25 14 26 19 27 16 28 26 29 18 30 19 31 29 32 21 33 26 34 24 35 32 36 30 37 33 38 33 39 30 40 32 41 32 42 32 43 37 44 36 45 37 46 35 47 43 48 46 49 45 50 39 51 43 52 49 53 48 54 ...
output:
18340
result:
ok single line: '18340'
Test #8:
score: 3.33333
Accepted
time: 1ms
memory: 6356kb
input:
50000 1 2 1 3 1 4 2 5 2 6 2 7 1 8 3 9 4 10 1 11 4 12 8 13 5 14 4 15 7 16 13 17 15 18 10 19 18 20 13 21 11 22 14 23 22 24 20 25 24 26 21 27 21 28 24 29 28 30 19 31 26 32 22 33 27 34 27 35 30 36 28 37 28 38 27 39 36 40 38 41 40 42 37 43 39 44 39 45 41 46 37 47 37 48 43 49 47 50 42 51 48 52 51 53 47 54...
output:
91709
result:
ok single line: '91709'
Test #9:
score: 3.33333
Accepted
time: 2ms
memory: 6932kb
input:
100000 1 2 1 3 1 4 2 5 3 6 5 7 5 8 3 9 7 10 1 11 4 12 5 13 3 14 3 15 5 16 13 17 14 18 17 19 16 20 12 21 10 22 14 23 12 24 19 25 15 26 19 27 20 28 25 29 20 30 28 31 25 32 23 33 25 34 29 35 29 36 26 37 36 38 35 39 28 40 31 41 36 42 40 43 40 44 35 45 43 46 41 47 39 48 40 49 47 50 45 51 49 52 47 53 52 5...
output:
183360
result:
ok single line: '183360'
Test #10:
score: 0
Wrong Answer
time: 0ms
memory: 3348kb
input:
20 2 2 1 3 2 4 3 5 1 6 4 7 6 8 5 9 8 10 1 11 4 12 6 13 4 14 10 15 11 16 4 17 6 18 9 19 5 20 14
output:
24
result:
wrong answer 1st lines differ - expected: '28', found: '24'
Test #11:
score: 0
Wrong Answer
time: 2ms
memory: 3344kb
input:
100 2 2 1 3 2 4 3 5 2 6 5 7 2 8 6 9 7 10 4 11 9 12 11 13 9 14 13 15 6 16 4 17 1 18 10 19 15 20 7 21 10 22 11 23 9 24 2 25 5 26 1 27 7 28 25 29 27 30 23 31 28 32 10 33 17 34 27 35 5 36 25 37 27 38 6 39 16 40 16 41 23 42 16 43 34 44 21 45 14 46 39 47 27 48 16 49 44 50 28 51 24 52 37 53 36 54 6 55 38 5...
output:
177
result:
wrong answer 1st lines differ - expected: '175', found: '177'
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 3388kb
input:
1000 2 2 1 3 2 4 2 5 3 6 3 7 3 8 2 9 7 10 3 11 10 12 8 13 11 14 6 15 11 16 10 17 16 18 3 19 1 20 13 21 4 22 1 23 14 24 19 25 19 26 4 27 15 28 13 29 14 30 12 31 16 32 23 33 32 34 21 35 26 36 21 37 17 38 12 39 24 40 30 41 39 42 23 43 29 44 43 45 44 46 15 47 38 48 21 49 14 50 36 51 40 52 3 53 14 54 23 ...
output:
1951
result:
wrong answer 1st lines differ - expected: '1953', found: '1951'
Test #13:
score: 0
Wrong Answer
time: 0ms
memory: 3636kb
input:
10000 2 2 1 3 1 4 3 5 2 6 2 7 6 8 2 9 6 10 6 11 6 12 1 13 8 14 2 15 1 16 13 17 5 18 8 19 5 20 3 21 1 22 20 23 21 24 7 25 23 26 24 27 1 28 23 29 7 30 28 31 25 32 8 33 4 34 19 35 7 36 24 37 26 38 12 39 19 40 36 41 19 42 26 43 37 44 27 45 32 46 17 47 5 48 15 49 15 50 19 51 33 52 8 53 19 54 45 55 30 56 ...
output:
19933
result:
wrong answer 1st lines differ - expected: '19934', found: '19933'
Test #14:
score: 3.33333
Accepted
time: 3ms
memory: 3668kb
input:
10000 2 2 1 3 2 4 1 5 1 6 1 7 6 8 6 9 4 10 6 11 7 12 1 13 2 14 1 15 11 16 5 17 11 18 6 19 11 20 15 21 13 22 11 23 3 24 4 25 16 26 17 27 14 28 20 29 3 30 10 31 10 32 18 33 9 34 32 35 12 36 33 37 18 38 34 39 32 40 25 41 25 42 31 43 20 44 7 45 5 46 42 47 29 48 7 49 31 50 7 51 23 52 16 53 6 54 3 55 33 5...
output:
19930
result:
ok single line: '19930'
Test #15:
score: 3.33333
Accepted
time: 9ms
memory: 4888kb
input:
50000 2 2 1 3 1 4 1 5 2 6 2 7 2 8 7 9 7 10 8 11 9 12 8 13 10 14 6 15 6 16 4 17 2 18 9 19 17 20 8 21 14 22 14 23 18 24 6 25 14 26 5 27 22 28 12 29 1 30 3 31 17 32 7 33 24 34 20 35 7 36 28 37 27 38 34 39 26 40 20 41 3 42 36 43 30 44 8 45 22 46 2 47 29 48 16 49 18 50 48 51 38 52 40 53 25 54 29 55 48 56...
output:
99922
result:
ok single line: '99922'
Test #16:
score: 0
Wrong Answer
time: 11ms
memory: 6576kb
input:
100000 2 2 1 3 2 4 1 5 2 6 1 7 1 8 7 9 1 10 9 11 8 12 1 13 2 14 9 15 10 16 5 17 16 18 17 19 12 20 14 21 15 22 14 23 15 24 17 25 23 26 1 27 20 28 17 29 23 30 6 31 11 32 14 33 24 34 27 35 16 36 5 37 24 38 12 39 12 40 9 41 19 42 3 43 33 44 13 45 3 46 35 47 38 48 14 49 10 50 45 51 14 52 41 53 15 54 53 5...
output:
199908
result:
wrong answer 1st lines differ - expected: '199910', found: '199908'
Test #17:
score: 3.33333
Accepted
time: 2ms
memory: 3400kb
input:
1000 2 2 1 3 2 4 3 5 2 6 2 7 4 8 4 9 2 10 8 11 10 12 7 13 2 14 4 15 7 16 10 17 11 18 13 19 9 20 13 21 20 22 15 23 14 24 17 25 19 26 23 27 22 28 17 29 19 30 21 31 21 32 24 33 28 34 29 35 28 36 32 37 31 38 36 39 36 40 29 41 30 42 33 43 37 44 35 45 42 46 40 47 38 48 39 49 45 50 49 51 44 52 42 53 50 54 ...
output:
1798
result:
ok single line: '1798'
Test #18:
score: 3.33333
Accepted
time: 0ms
memory: 3524kb
input:
2000 2 2 1 3 2 4 2 5 4 6 1 7 5 8 7 9 3 10 9 11 3 12 3 13 6 14 3 15 10 16 12 17 12 18 7 19 17 20 17 21 20 22 13 23 12 24 21 25 20 26 24 27 24 28 17 29 28 30 19 31 20 32 21 33 30 34 28 35 33 36 33 37 30 38 33 39 34 40 33 41 37 42 31 43 34 44 40 45 37 46 38 47 43 48 37 49 44 50 44 51 47 52 46 53 46 54 ...
output:
3615
result:
ok single line: '3615'
Test #19:
score: 3.33333
Accepted
time: 2ms
memory: 5668kb
input:
10000 2 2 1 3 1 4 2 5 1 6 2 7 5 8 7 9 6 10 1 11 4 12 4 13 8 14 11 15 13 16 11 17 8 18 16 19 12 20 15 21 17 22 11 23 15 24 20 25 20 26 15 27 20 28 24 29 28 30 19 31 22 32 30 33 28 34 29 35 25 36 33 37 33 38 31 39 28 40 34 41 36 42 39 43 36 44 41 45 39 46 40 47 39 48 47 49 42 50 43 51 46 52 48 53 47 5...
output:
18240
result:
ok single line: '18240'
Test #20:
score: 0
Wrong Answer
time: 11ms
memory: 5360kb
input:
50000 2 2 1 3 2 4 1 5 3 6 2 7 2 8 2 9 8 10 4 11 7 12 9 13 11 14 9 15 13 16 9 17 14 18 15 19 14 20 15 21 10 22 12 23 13 24 20 25 21 26 17 27 23 28 22 29 26 30 26 31 25 32 22 33 25 34 32 35 25 36 28 37 27 38 30 39 32 40 36 41 36 42 35 43 36 44 41 45 44 46 44 47 40 48 42 49 42 50 48 51 40 52 48 53 44 5...
output:
83258
result:
wrong answer 1st lines differ - expected: '91573', found: '83258'
Test #21:
score: 0
Wrong Answer
time: 6ms
memory: 6612kb
input:
80000 2 2 1 3 1 4 1 5 4 6 5 7 2 8 5 9 6 10 1 11 1 12 9 13 2 14 6 15 11 16 13 17 6 18 14 19 10 20 10 21 17 22 19 23 14 24 23 25 24 26 18 27 23 28 23 29 25 30 27 31 27 32 27 33 26 34 28 35 26 36 28 37 31 38 28 39 35 40 37 41 34 42 32 43 34 44 42 45 42 46 37 47 38 48 44 49 38 50 44 51 48 52 47 53 43 54...
output:
133068
result:
wrong answer 1st lines differ - expected: '146479', found: '133068'
Test #22:
score: 0
Wrong Answer
time: 17ms
memory: 7560kb
input:
100000 2 2 1 3 1 4 1 5 4 6 2 7 6 8 2 9 8 10 4 11 10 12 11 13 8 14 6 15 8 16 7 17 14 18 16 19 17 20 15 21 10 22 12 23 17 24 16 25 20 26 20 27 24 28 17 29 20 30 23 31 23 32 31 33 26 34 33 35 27 36 32 37 28 38 27 39 37 40 34 41 33 42 37 43 32 44 39 45 38 46 38 47 38 48 47 49 46 50 41 51 44 52 43 53 42 ...
output:
166566
result:
wrong answer 1st lines differ - expected: '183232', found: '166566'
Test #23:
score: 0
Wrong Answer
time: 4ms
memory: 3656kb
input:
10000 2 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 5 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 33 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53 5...
output:
19487
result:
wrong answer 1st lines differ - expected: '19495', found: '19487'
Test #24:
score: 0
Wrong Answer
time: 1ms
memory: 3672kb
input:
10000 2 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53 ...
output:
18901
result:
wrong answer 1st lines differ - expected: '18913', found: '18901'
Test #25:
score: 0
Wrong Answer
time: 4ms
memory: 4904kb
input:
50000 2 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53 ...
output:
98130
result:
wrong answer 1st lines differ - expected: '98142', found: '98130'
Test #26:
score: 0
Wrong Answer
time: 4ms
memory: 5892kb
input:
50000 2 2 1 3 2 4 3 5 4 6 5 7 2 8 6 9 3 10 2 11 4 12 4 13 7 14 9 15 5 16 14 17 4 18 8 19 13 20 5 21 13 22 3 23 2 24 17 25 8 26 8 27 17 28 15 29 25 30 17 31 7 32 24 33 12 34 29 35 21 36 22 37 4 38 26 39 14 40 27 41 34 42 14 43 10 44 11 45 23 46 16 47 34 48 10 49 2 50 41 51 43 52 28 53 2 54 12 55 54 5...
output:
99954
result:
wrong answer 1st lines differ - expected: '99957', found: '99954'
Test #27:
score: 3.33333
Accepted
time: 5ms
memory: 5860kb
input:
50000 2 2 1 3 2 4 1 5 4 6 4 7 4 8 5 9 1 10 5 11 6 12 7 13 5 14 13 15 4 16 3 17 8 18 12 19 11 20 11 21 18 22 11 23 14 24 21 25 1 26 10 27 7 28 11 29 14 30 8 31 5 32 26 33 6 34 30 35 12 36 32 37 16 38 20 39 15 40 38 41 22 42 31 43 11 44 21 45 10 46 36 47 41 48 34 49 7 50 30 51 6 52 20 53 45 54 36 55 2...
output:
99970
result:
ok single line: '99970'
Test #28:
score: 3.33333
Accepted
time: 11ms
memory: 6412kb
input:
100000 2 2 1 3 1 4 1 5 4 6 5 7 2 8 3 9 8 10 4 11 4 12 11 13 4 14 12 15 12 16 1 17 2 18 17 19 10 20 7 21 7 22 17 23 6 24 10 25 7 26 16 27 19 28 26 29 14 30 27 31 5 32 28 33 3 34 9 35 27 36 14 37 15 38 36 39 31 40 23 41 31 42 32 43 5 44 7 45 9 46 6 47 43 48 30 49 39 50 23 51 15 52 34 53 31 54 51 55 9 ...
output:
199971
result:
ok single line: '199971'
Test #29:
score: 0
Wrong Answer
time: 13ms
memory: 6412kb
input:
100000 2 2 1 3 2 4 1 5 2 6 5 7 5 8 6 9 5 10 8 11 1 12 6 13 10 14 5 15 12 16 10 17 11 18 9 19 5 20 1 21 9 22 19 23 14 24 8 25 22 26 10 27 4 28 20 29 19 30 11 31 17 32 11 33 7 34 2 35 10 36 4 37 19 38 21 39 25 40 28 41 1 42 37 43 28 44 6 45 43 46 11 47 8 48 39 49 12 50 39 51 35 52 43 53 37 54 47 55 7 ...
output:
199947
result:
wrong answer 1st lines differ - expected: '199949', found: '199947'
Test #30:
score: 0
Wrong Answer
time: 11ms
memory: 6400kb
input:
100000 2 2 1 3 1 4 3 5 1 6 2 7 1 8 5 9 2 10 7 11 1 12 7 13 6 14 9 15 6 16 15 17 12 18 16 19 11 20 18 21 6 22 6 23 3 24 18 25 1 26 6 27 16 28 15 29 27 30 10 31 22 32 27 33 30 34 33 35 4 36 2 37 34 38 1 39 3 40 39 41 12 42 22 43 35 44 8 45 19 46 34 47 32 48 40 49 28 50 1 51 41 52 45 53 15 54 26 55 32 ...
output:
199973
result:
wrong answer 1st lines differ - expected: '199976', found: '199973'