比赛 |
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;
}