魏总数星星

声明

好像是别人的原创题,感觉不错:来源
另外,学习并查集可以参考这个:生动的故事,透彻的分析
我的并查集总结

题目

「问题大意」
魏总,也就是dp魏,灰常喜欢星星,有一天他躺在草坪上数星星。天上共有i颗星星,魏总把天空分成了K个扇形,绕着天空的中心——月亮排布。月亮看见魏总喜欢星星,灰常不爽,她就想考一下魏总。
月亮给出n队星星的相互关系,形如a b p表示b星星在a星星所在扇形区域的顺时针方向第p个扇形内(0<=p<=k)(p==0时表示在同一个扇形内)。最后月亮要询问m次,形如a b表示询问a b两星是否在一个扇形内,是则输出“Yes”,不是则输出“No”,不知道则输出“Unknown”。
由于月亮看魏总喜欢星星变得心情急躁,可能有一些关系与前面的关系矛盾,则这些关系无效。月亮说如果不能把她的所有询问答对就要发出强光,让魏总看不到星星,而本来是大神的魏总因为想见到星星不能编程,只有把这个艰巨的任务交给你了。
「输入格式」
第一行四个整数i,k,n,m表示i颗星星,k个扇形,n个关系,m次询问。
接下来n行,每行三个整数a b p 表示表示b星星在a星星所在扇形区域的顺时针方向第p个扇形内。
接下来m行,每行两个整数a b表示询问a,b是否在同一个扇形内。
「输出格式」
共m行,每行为“Yes”或“No”或“Unknown”对应每一个询问
「输入样例」
5 5 3 3
1 2 1
2 4 2
4 5 2
1 2
3 4
1 5
「输出样例」
No
Unknown
Yes
「数据范围」
20%,魏总数不超过100个星星,月亮询问不超过100次,天空被分成不超过10个区域。
50%,魏总数不超过4000个星星,月亮询问不超过4000次,天空被分成不超过1000个区域。
100%,魏总数不超过100000个星星,月亮询问不超过100000次,天空被分成不超过10000个区域,关系数少于200000。

代码

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
struct star
{
int fa,len;
star()
{
fa=len=0;
};
}st[100010];
int mod;
int findfa(int now)
{
if(st[now].fa==now) return now;
int f=findfa(st[now].fa);
st[now].len=(st[now].len+st[st[now].fa].len)%mod;
if (st[now].len==0) st[now].len=mod;
st[now].father=f;
return f;
}
void join(int a,int b,int l)
{
int af=findfa(a),bf=findfa(b);
int len=(st[a].len+l)%mod;
st[bf].fa=a;
if (l>=st[b].len) st[bf].len=l-st[b].len;
else st[bf].len=mod+l-st[b].len;
}
int main()
{
int n,m,k;
cin>>n>>mod>>m>>k;
for(int i=1;i<=n;i++) st[i].fa=i;
for(int i=1;i<=m;i++)
{
int a,b,p;
cin>>a>>b>>p;
if(findfa(a)!=findfa(b)) join(a,b,p);
}
for(int i=1;i<=k;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if (findfa(a)!=findfa(b)) printf("Unknown\n");
else
{
if (st[a].len%mod==st[b].len%mod) printf("Yes\n");
else printf("No\n");
}
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/4672.html
转载请注明出处,谢谢!