QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317675#7936. Eliminate Treeone_god_and_two_dogs#WA 1ms3584kbC++171.0kb2024-01-29 13:14:382024-01-29 13:14:39

Judging History

你现在查看的是最新测评结果

  • [2024-01-29 13:14:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3584kb
  • [2024-01-29 13:14:38]
  • 提交

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'