QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#358656 | #6307. Chase Game 2 | Djangle162857# | WA | 10ms | 10064kb | C++20 | 2.0kb | 2024-03-19 22:07:31 | 2024-03-19 22:07:32 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
using namespace std;
const int N=200010;
int n,cnt,c[N];
struct Graph {
int tot,root,ind[N],head[N],suiv[N<<1],ver[N<<1],dis[N<<1],
fa[N<<1];
inline void init()
{
for(int i=0; i<=tot; i++)
head[i]=dis[i]=ind[i]=fa[i]=0;
root=tot=0;
}
inline void lnk(int x,int y)
{
ver[++tot]=y;
suiv[tot]=head[x];
head[x]=tot;
ind[y]++;
}
inline void dfs(int x)
{
// cout << "dfs " << x << endl;
dis[x]=dis[fa[x]]+1;
if(dis[x]>dis[root])
root=x;
for(int i=head[x]; i; i=suiv[i]) {
int y=ver[i];
if(y==fa[x])
continue;
fa[y]=x;
dfs(y);
}
}
} e;
inline void sol()
{
cnt=0;
e.init();
scanf("%d",&n);
for(int i=1,x,y; i<n; i++)
scanf("%d%d",&x,&y),e.lnk(x,y),e.lnk(y,x);
int ind_cnt=0;
for(int i=1; i<=n; i++) {
if(e.ind[i]>1)
ind_cnt++;
}
if(ind_cnt<=1) {
puts("-1");
return;
}
e.dfs(1);
e.dis[e.root]=1;
e.fa[e.root]=0;
e.dfs(e.root);
for(int i=e.root; i; i=e.fa[i]) {
c[++cnt]=i;
}
// for (int i = 1; i <= cnt; i++)
// cout << c[i] << endl;
// cout << endl;
ind_cnt=0;
int leaf=0,ans=0,maxiind=0;
for(int i=1;i<=n;i++)
if(e.ind[i]==1)leaf++;
for(int i=2; i<cnt; i++) {
if(e.ind[c[i]]>2)
ind_cnt++;
if(i==2||i==cnt-1)
maxiind=max(maxiind,e.ind[c[i]]-1);
else maxiind=max(maxiind,e.ind[c[i]]-2);
}
if(!ind_cnt)
ans=leaf/2;
else ans=max((leaf+1)>>1,maxiind);
printf("%d\n",ans);
}
signed main()
{
int T;
scanf("%d",&T);
while(T--)
sol();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10064kb
input:
4 2 1 2 4 1 2 2 3 3 4 4 1 2 2 3 2 4 5 1 2 2 3 3 4 3 5
output:
-1 1 -1 2
result:
ok 4 number(s): "-1 1 -1 2"
Test #2:
score: 0
Accepted
time: 6ms
memory: 9980kb
input:
10000 4 1 2 1 3 3 4 4 1 2 1 3 1 4 4 1 2 2 3 1 4 5 1 2 2 3 1 4 4 5 5 1 2 2 3 3 4 4 5 4 1 2 2 3 2 4 5 1 2 1 3 2 4 2 5 4 1 2 2 3 1 4 5 1 2 1 3 2 4 1 5 5 1 2 2 3 3 4 2 5 5 1 2 1 3 2 4 2 5 4 1 2 1 3 3 4 5 1 2 1 3 3 4 1 5 4 1 2 1 3 1 4 5 1 2 1 3 3 4 3 5 5 1 2 2 3 3 4 3 5 4 1 2 1 3 2 4 5 1 2 2 3 2 4 3 5 5 ...
output:
1 -1 1 1 1 -1 2 1 2 2 2 1 2 -1 2 2 1 2 2 1 1 1 -1 2 2 2 1 -1 1 1 2 1 1 -1 1 2 1 1 1 -1 1 1 2 2 2 1 1 1 -1 1 2 1 1 2 1 2 1 1 2 -1 -1 -1 2 2 2 1 1 1 2 2 2 -1 1 2 -1 1 1 -1 2 -1 -1 1 2 2 2 1 1 1 1 1 1 1 1 1 2 -1 1 1 2 -1 2 1 1 1 -1 2 -1 1 -1 -1 2 -1 2 1 2 2 1 1 1 1 2 1 1 1 1 -1 2 1 2 1 1 1 1 1 1 1 2 -1...
result:
ok 10000 numbers
Test #3:
score: -100
Wrong Answer
time: 10ms
memory: 9988kb
input:
10000 9 1 2 2 3 3 4 4 5 1 6 6 7 5 8 7 9 9 1 2 2 3 2 4 1 5 2 6 4 7 6 8 1 9 9 1 2 2 3 1 4 4 5 5 6 4 7 2 8 1 9 10 1 2 2 3 1 4 3 5 3 6 2 7 6 8 6 9 6 10 10 1 2 1 3 3 4 2 5 1 6 5 7 4 8 2 9 7 10 10 1 2 2 3 2 4 1 5 3 6 6 7 5 8 4 9 9 10 9 1 2 2 3 2 4 1 5 3 6 2 7 1 8 2 9 9 1 2 1 3 2 4 1 5 3 6 3 7 7 8 8 9 10 1...
output:
1 3 3 3 2 2 3 2 3 2 3 2 3 2 3 3 3 2 3 2 3 2 3 3 2 2 3 3 3 3 3 3 2 3 3 3 4 3 3 3 2 3 3 3 3 3 2 3 3 3 3 3 3 2 3 2 3 2 2 3 3 4 3 4 3 3 2 2 3 2 2 2 3 3 2 3 3 2 4 3 3 3 2 3 2 2 3 3 3 3 2 3 3 2 3 3 3 3 3 2 3 2 2 3 5 3 3 2 2 3 2 3 4 2 5 3 2 3 3 2 3 2 3 3 3 3 2 2 3 3 3 2 3 3 3 3 3 3 2 3 3 2 2 4 3 3 3 3 2 3 ...
result:
wrong answer 170th numbers differ - expected: '3', found: '4'