QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#283781 | #6307. Chase Game 2 | FHQY_WWW# | WA | 5ms | 12432kb | C++20 | 1.9kb | 2023-12-15 14:25:28 | 2023-12-15 14:25:29 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define double long double
#define lowbit(x) x&(-x)
#define fastios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define el puts("")
#define udm unordered_map<int,int>
#define set_0(a) memset(&a,0,sizeof(a))
#define set_unint(a) memset(&a,-1,sizeof(a))
using namespace std;
//define_var
const int M=2e5+9,inf=1e18;
vector<int> edge[M];
int dp[M][2],ld;
int cnt[M];
multiset<int> st;
//define_var
//function_begin
int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
void dfs(int u,int f)
{
dp[u][0]=dp[u][1]=0;
bool flag=0;
for(auto i : edge[u])
{
if(i==f) continue;
flag=1;
dfs(i,u);
int tmp=dp[i][1]+1;
if(tmp>=dp[u][1])
dp[u][0]=dp[u][1],dp[u][1]=tmp;
else if(tmp>=dp[u][0])
dp[u][0]=tmp;
}
ld=max(ld,dp[u][0]+dp[u][1]);
if(!flag)
cnt[f]++;
}
//function_end
//solve_begin
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
edge[i].clear();
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
dp[i][0]=dp[i][1]=0;
cnt[i]=0;
}
ld=0;
int ans=0;
st.clear();
dfs(1,0);
if(ld<3)
{
cout<<-1<<endl;
return;
}
for(int i=1;i<=n;i++)
if(cnt[i]) st.insert(cnt[i]);
while(!st.empty())
{
if(st.size()==1)
ans+=*st.begin(),st.clear();
else
{
int n1=*(--st.end());
st.erase(--st.end());
int n2=*(--st.end());
st.erase(--st.end());
n1--,n2--,ans++;
if(n1) st.insert(n1);
if(n2) st.insert(n2);
}
}
cout<<ans<<endl;
}
//solve_end
//main_begin
signed main()
{
fastios
int T=1;
cin>>T;
while(T--)
solve();
}
//main_end
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12432kb
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: -100
Wrong Answer
time: 5ms
memory: 12164kb
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 1 2 1 2 -1 2 2 1 1 2 1 1 1 -1 2 1 2 1 -1 1 1 2 1 2 -1 1 2 2 1 2 -1 2 2 2 2 2 1 1 1 -1 1 1 1 1 1 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 1 1 1 1 1 1 1 1 2 2 2 -1 1 2 2 -1 2 1 1 1 -1 2 -1 1 -1 -1 2 -1 2 1 2 2 1 1 1 1 1 1 1 1 1 -1 1 1 2 1 1 1 1 1 1 1 2 -1...
result:
wrong answer 10th numbers differ - expected: '2', found: '1'