状态: Unaccepted
测评机: Xeost[5]
得分: 10分
提交日期: 2010-7-15 8:29:00
有效耗时: 171毫秒
测试结果1: 通过本测试点|有效耗时171ms
测试结果2: 运行错误|栈溢出
测试结果3: 运行错误|栈溢出
测试结果4: 运行错误|栈溢出
测试结果5: 运行错误|栈溢出
测试结果6: 运行错误|栈溢出
测试结果7: 运行错误|栈溢出
测试结果8: 运行错误|栈溢出
测试结果9: 运行错误|栈溢出
测试结果10: 运行错误|栈溢出
提交代码:
var
i,j,n,m,p,t1,t,t2,f1,f2:longint;
s:array[1..2008] of string;
s1,s2:string;
fa:array[1..2008] of integer;
function find(x:longint):longint;
begin
if fa[x]=0 then exit(x);
find:=find(fa[x]);
fa[x]:=find;
end;
begin
readln(n,m,p);
for i:=1 to n do
begin
fa[i]:=0;
end;
for i:=1 to n do
readln(s[i]);
for i:=1 to m do
begin
readln(s1);
t:=pos(' ',s1);
s2:=copy(s1,1,t-1);
delete(s1,1,t);
t1:=0;t2:=0;
for j:=1 to n do
if s[j]=s1 then t1:=j
else if s[j]=s2 then t2:=j;
while fa[t1]<>0 do
begin
t1:=fa[t1];
end;
fa[t1]:=t2;
end;
for i:=1 to p do
begin
readln(s1);
t:=pos(' ',s1);
s2:=copy(s1,1,t-1);
delete(s1,1,t);
t1:=0;t2:=0;
for j:=1 to n do
if s[j]=s1 then t1:=j
else if s[j]=s2 then t2:=j;
f1:=find(t1);f2:=find(t2);
if f1=f2 then writeln('safe')
else writeln('cc cry');
end;
end.
for j:=1 to n do
if s[j]=s1 then t1:=j
else if s[j]=s2 then t2:=j;
哥们,你这么裸找对应的序号,是不是太暴力了~
有以下三种方案
1:String Hash
2:C++ Map
3:Qsort + Binary Search
4:BST(Orz)
5:TRIE
var
i,j,n,m,p,t1,t,t2,f1,f2:longint;
s:array[1..2008] of string;
s1,s2:string;
fa:array[1..2008] of integer;
function find(x:longint):longint;
begin
if x=0 then exit(0);
if fa[x]=x then exit(x);
find:=find(fa[x]);
fa[x]:=find;
end;
begin
readln(n,m,p);
for i:=1 to n do
begin
fa[i]:=i;
end;
for i:=1 to n do
readln(s[i]);
for i:=1 to m do
begin
readln(s1);
t:=pos(' ',s1);
s2:=copy(s1,1,t-1);
delete(s1,1,t);
t1:=0;t2:=0;
for j:=1 to n do
if s[j]=s1 then t1:=j
else if s[j]=s2 then t2:=j;
t1:=find(t1);
t2:=find(t2);
if t1<>t2 then fa[t1]:=t2;
end;
for i:=1 to p do
begin
readln(s1);
t:=pos(' ',s1);
s2:=copy(s1,1,t-1);
delete(s1,1,t);
t1:=0;t2:=0;
for j:=1 to n do
if s[j]=s1 then t1:=j
else if s[j]=s2 then t2:=j;
f1:=find(t1);f2:=find(t2);
if f1=f2 then writeln('safe')
else writeln('cc cry');
end;
end.