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

AT_abc328_f.[ABC328F] Good Set Query

提高+/省选-

通过率：0%

AC君温馨提醒

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

题目描述

题目内容

给定 QQ 个三元组 (a1,b1,d1),(a2,b2,d2),...,(aQ,bQ,dQ)(a_1,b_1,d_1),(a_2,b_2,d_2),...,(a_Q,b_Q,d_Q) 。

集合 1,2,...,Q{1,2,...,Q} 的一个子集 SS 被定义为好的子集，当且仅当存在一个长度为 NN 的序列 (X1,X2,...,XN)(X_1,X_2,...,X_N) 满足以下条件：

对于所有 i∈Si\in S ， Xai−Xbi=diX_{a_i}-X_{b_i}=d_i 。

将 SS 初始化为空集，对于 i=1,2,...,Qi=1,2,...,Q 依次进行以下操作：

如果 S∪{i}S\cup \{i\} 是一个好的集合，那么将 SS 替换成 S∪{i}S\cup \{i\} 。

以升序输出 SS 中的所有元素。

输入格式

从标准输入流读入，格式如下：

NQa1b1d1a2b2d2...aQbQdQN\quad Q\\ a_1\quad b_1\quad d_1\\ a_2\quad b_2\quad d_2\\ .\\ .\\ .\\ a_Q\quad b_Q\quad d_Q\\

输出格式

以升序按照以下格式输出集合 SS 中的所有元素 (s1,s2,...,sk)(s_1,s_2,...,s_k) ：

s1s2...sks_1\quad s_2\quad ...\quad s_k

输入输出样例

  • 输入#1

    3 5
1 2 2
3 2 -3
2 1 -1
3 3 0
1 3 5

    输出#1

    1 2 4 5

  • 输入#2

    200000 1
1 1 1

    输出#2

  • 输入#3
    5 20
4 2 125421359
2 5 -191096267
3 4 -42422908
3 5 -180492387
3 3 174861038
2 3 -82998451
3 4 -134761089
3 1 -57159320
5 2 191096267
2 4 -120557647
4 2 125421359
2 3 142216401
4 5 -96172984
3 5 -108097816
1 5 -50938496
1 2 140157771
5 4 65674908
4 3 35196193
4 4 0
3 4 188711840
    输出#3
    1 2 3 6 8 9 11 14 15 16 17 19
说明/提示
    

  • 所有输入元素为整数。
    • 

  • 1≤N,Q≤2×1051\le N,Q\le 2\times 10^5
    • 

  • 1≤ai,bi≤N1\le a_i,b_i\le N
    • 

  • −109≤di≤109-10^9\le d_i\le 10^9
    • 



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