比赛 20120718 评测结果 AAAAATTTTT
题目名称 座位问题 最终得分 50
用户昵称 了反取字名我擦 运行时间 5.383 s
代码语言 C++ 内存使用 2.98 MiB
提交时间 2012-07-18 10:27:22
显示代码纯文本
#include<fstream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;
ifstream fi("seat.in");
ofstream fo("seat.out");

struct point
{
	vector<int>line;
	int seated;
	int fg;
}map[100001];
int n,people;
struct
{
	int data[100001];
	int dr[100001];
	int head,tail;
	void init()
	{
		head=0;tail=0;
	}
	void push_back(int k,int l)
	{
		data[tail]=k;
		dr[tail]=l;
		if(tail<100000)
			tail++;
		else
			tail=0;
	}
	int front()
	{
		if(head<100000)
			return dr[head];
		else
			return dr[head];
	}
	int pop_front()
	{
		if(head<100000)
		{
			head++;
			return data[head-1];
		}
		else
		{
			head=0;
			return data[100000];
		}
	}
}queue;
void bfs(int p,int dr,int k)
{
	if(k==p){map[k].seated=1;fo<<dr<<endl;}
	else
	{
		for(int i=0;i<map[p].line.size();i++)
		{
			if(map[map[p].line[i]].fg==0)
				queue.push_back(map[p].line[i],dr+map[p].seated);
		}
		map[p].fg=1;
		int t1,t2;
		t2=queue.front();t1=queue.pop_front();
		bfs(t1,t2,k);
		map[p].fg=0;
	}
}
int main()
{
	fi>>n;
	for(int i=0;i<=n;i++)
	{
		map[i].seated=0;
		map[i].fg=0;
	}
	int t1,t2;
	for(int i=0;i<n-1;i++)
	{
		fi>>t1>>t2;
		map[t1].line.push_back(t2);
		map[t2].line.push_back(t1);
	}
	for(int i=0;i<n;i++)
	{
		queue.init();
		fi>>people;
		bfs(1,0,people);
	}
	fi.close();
	fo.close();
	return 0;
}