QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#317675 | #7936. Eliminate Tree | one_god_and_two_dogs# | WA | 1ms | 3584kb | C++17 | 1.0kb | 2024-01-29 13:14:38 | 2024-01-29 13:14:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll=long long ;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n;
cin>>n;
vector<vector<int>>G(n);
vector<int>deg(n),del(n);
for(int i=1;i<n;++i){
int a,b;
cin>>a>>b;
--a,--b;
++deg[a],++deg[b];
G[a].emplace_back(b);
G[b].emplace_back(a);
}
priority_queue<tuple<int,int,int>>que;
for(int i=0;i<n;++i)if(deg[i]==1)
que.emplace(-deg[G[i][0]],G[i][0],i);
int ans=0;
while(!que.empty()){
auto [fd,fa,id]=que.top();
que.pop();
if(del[fa])continue;
fd=-fd;
int x=fa;
del[id]=1;
--deg[x];
--deg[id];
if(fd<=2){
ans++;
if(!del[x]){
del[x]=1;
for(auto y:G[x]){
if(!del[y]&&--deg[y]==1){
int d=0;
for(auto z:G[y]){
if(!del[z]){
d=z;
}
}
que.emplace(-deg[d],d,y);
}
}
}
}else {
ans+=2;
if(!del[x]&&--deg[x]==1){
int d=0;
for(auto y:G[x]){
if(!del[y]){
d=y;
}
}
que.emplace(-deg[d],d,x);
}
}
}
cout<<ans<<endl;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3584kb
input:
5 1 2 2 3 3 4 3 5
output:
5
result:
wrong answer 1st numbers differ - expected: '4', found: '5'