QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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;
}
Details
Tip: Click on the bar to expand more detailed information
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'