题目详情题解（0）讨论（0）提交记录（0）

AT_arc036_d.[ARC036D] 偶数メートル

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥君所在的国家有 NN 座城市，编号为 11 到 NN。初始时没有道路，于是国家准备修建几条连接不同城市的双向道路。

由于高桥君很喜欢偶数，所以在从一座城市到达另外一座城市时，即使绕远路，或者走同一条路多次，也要使得走的总距离为偶数。但是在走过一条路后，高桥君不会马上再走一遍这条路。

高桥君有时会指定两座不同的城市，问他是否能用上述方式从其中一座走到另外一座。

由于国家还在建设道路，因此在不同时间提出的相同问题可能有不同的答案。

输入格式

第一行两个整数 N,Q(1≤N,Q≤105)N,Q(1\le N,Q\le 10^5)，表示城市数量和操作数量。

接下来 QQ 行每行四个整数 w,x,y,z(1≤w≤2,1≤x,y≤N,x≠y,1≤z≤105)w,x,y,z(1\le w\le2,1\le x,y\le N,x\ne y,1\le z\le 10^5)。

  • w=1w=1，表示国家在 xx 和 yy 两座城市中修了一条长度为 zz 的双向道路。
  • w=2w=2，表示高桥君询问城市 xx 和 yy 能否通过他的走路方式互相到达，保证此时 z=1z=1。

注意：

  • 相同的两座城市间可能有多条道路。
  • 高桥君每次提问时，之前所有的道路都已建设完毕。

输出格式

对于每次高桥君的询问，若可行输出 YES，否则输出 NO。

by @Larryyu

输入输出样例

  • 输入#1

    5 9
1 1 2 3
1 1 3 2
1 3 5 5
2 1 5 1
2 2 5 1
1 2 4 4
1 1 4 6
2 1 5 1
2 3 5 1

    输出#1

    NO
YES
YES
YES

  • 输入#2

    5 7
1 1 2 3
1 2 4 4
1 5 3 1
2 1 3 1
2 5 3 1
1 3 1 2
2 3 4 1

    输出#2

    NO
NO
NO

  • 输入#3

    3 6
1 1 2 1
1 1 3 3
1 2 3 2
1 2 1 2
2 1 3 1
2 2 3 1

    输出#3

    YES
YES

输入解题思路，AI测评打分。不知道怎么写?

首页