「vijos1876」小岛的标号
描述
Xiaodao是一位喜欢参加ACM比赛的孩子.
所谓ACM比赛, 是一种团队比赛.
每一次比赛, 每队需要由恰好三位选手组成.
现在, Xiaodao希望组建一支新的队伍, 在这之前, 他需要知道每一位朋友有多少可能成为自己的好队友.
他计划给每一位朋友做出一个等级标号.
Xiaodao本人的等级标号为0.
如果一位朋友曾经和Xiaodao组队参加过比赛, 那么就标号为1.
如果一位朋友并没有与Xiaodao组队参加过比赛, 但是曾经与一位”与Xiaodao一起参加过比赛的人”组队参加过比赛. 那么就标号为2.
如果一位朋友无法标号为小于等于 k 的整数, 但是曾经与”标号为k的人”一起参加过比赛, 那么便可以标号为k+1.
其余的朋友们, 便无法给出编号, 我们记为”undefined”.
现在, 我们给出了 n 组曾经参赛过的队伍, 每一组中给出了三位选手的名字.
我们希望知道每一位涉及到的选手应该被给予什么样的标号.
格式
输入格式
第一行给出队伍的总数 n (1<=n<=50000).
之后 n 行, 每一行给出了一支队伍中三位选手的名字, 用空格隔开.
每一位选手的名字都是一个非空的英文字符串, 其长度不超过 20. 首字母大写, 其余字母小写.
输出格式
对于输入数据涉及到的所有选手, 需要按照其名字的字典序输出每一位选手的名字与标号.
每一行输出一位选手的信息, 首先是他(她)的名字, 其次是他(她)的标号, 如果标号无法给出, 则输出 “undefined”.
样例1
样例输入1[复制]
样例输出1[复制]
限制
对于40%的数据: 1<=n<=100
对于80%的数据: 1<=n<=10000
对于100%的数据: 1<=n<=50000
时间限制: 每个测试点2秒.
题解。。。map+bfs。。。
map显然不能过100的数据。。。100还是字典树吧
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<map> using namespace std; map<string,int> point; char t[30]="Xiaodao"; int n,cnt,tot; int q[10005],last[10005]; int mark[10005]; string ch[10005]; struct data{int to,next;}e[60005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void bfs() { int head=0,tail=1; int st=point[t]; q[head]=st;mark[st]=1; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(!mark[e[i].to]) { mark[e[i].to]=mark[now]+1; q[tail++]=e[i].to; } } } int main() { scanf("%d",&n); char a[30],b[30],c[30]; int t1,t2,t3; for(int i=1;i<=n;i++) { scanf("%s",a);scanf("%s",b);scanf("%s",c); t1=point[a];t2=point[b];t3=point[c]; if(!t1)tot++,ch[tot]+=a,t1=point[a]=tot; if(!t2)tot++,ch[tot]+=b,t2=point[b]=tot; if(!t3)tot++,ch[tot]+=c,t3=point[c]=tot; insert(t1,t2);insert(t2,t3);insert(t1,t3); } bfs(); sort(ch+1,ch+tot+1); for(int i=1;i<=tot;i++) { int l=ch[i].length(); for(int j=0;j<l;j++)printf("%c",ch[i][j]); int t=point[ch[i]]; if(mark[t]==0)puts(" undefined"); else printf(" %d\n",mark[t]-1); } return 0; } |
OI 课件=>
