TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5961
  • 問題
  • P5961「IOI2019」景点划分
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 2s,1024m
    問題説明

    巴库有 \(n\) 处景点。从 $0$ 到 \(n-1\) 编号。另外还有 \(m\) 条双向道路,从 $0$ 到 \(m-1\) 编号。每条道路连接两个不同的景点。经由这些道路,可以在任意两处景点之间往来。

    Fatima 打算在三天之内参观完所有这些景点。她已经决定要在第一天参观 \(a\) 处景点,第二天参观 \(b\) 处景点,第三天参观 \(c\) 处景点。因此,她要把这 \(n\) 处景点划分为三个集合 \(A,B\)\(C\),其规模分别为 \(a,b\)\(c\)。每处景点恰好属于其中一个集合,因此有 \(a+b+c=n\)

    Fatima 想要找到这样的集合划分 \(A,B\)\(C\),使得这三个集合中的至少两个连通的。一个景点集合 \(S\) 被称为是连通的,如果能够经由这些道路在 \(S\) 中的任意两处景点之间往来,且不需要经过不在 \(S\) 中的景点。如果满足上述要求,则景点的一个划分 \(A,B\)\(C\) 被称为是合法的

    请帮助 Fatima 找到一个合法的景点划分(给定 \(a,b\)\(c\)),或者判定合法的划分不存在。如果存在多个合法的划分,你可以给出其中的任意一个。

    入力形式

    第一行两个整数 \(n,m\),分别表示景点数与道路数;

    第二行三个整数 \(a,b,c\),表示集合 \(A,B\)\(C\) 的期望规模;

    接下来 \(m\) 行,第 \(i\) 行两个整数 \(p_i,q_i\),表示编号为 \(p_i\) 的景点和编号为 \(q_i\) 的景点之间有一条双向道路。

    出力形式

    输出一行 \(n\) 个整数,每两个整数之间用一个空格隔开。如果不存在合法的划分,输出的 \(n\) 个整数均为 $0$。否则,对于输出的第 \(i\) 个整数 \(s_i\),应为 $1,2$ 或 $3$ 中的一个,表示景点 \(i-1\) 被归到集合 \(A,B\)\(C\)

    ヒント

    样例输入 1

    9 10
    4 2 3
    0 1
    0 2
    0 3
    0 4
    0 6
    0 8
    1 7
    3 7
    4 5
    5 6
    

    样例输出 1

    1 1 3 1 2 2 3 1 3
    

    样例说明 1

    split1.png

    一个可能的正确解为 \([1,1,3,1,2,2,3,1,3]\)。这个解刻画了这样的划分:\(A=\{0,1,3,7\},B=\{4,5\}\)\(C=\{2,6,8\}\)。集合 \(A\)\(B\) 是连通的。

    样例输入 2

    6 5
    2 2 2
    0 1
    0 2
    0 3
    0 4
    0 5
    

    样例输出 2

    0 0 0 0 0 0
    

    样例说明 2

    split2.png

    合法的划分不存在。因此,唯一的正确答案是 \([0,0,0,0,0,0]\)

    对于所有数据:

    • $3\le n\le 10^5$;
    • $2\le m\le 2\times 10^5$;
    • $1\le a,b,c\le n,a+b+c=n$;
    • 每一对景点之间至多有一条道路;
    • 经由这些道路,可以在任意两处景点之间往来;
    • 对于 $1\le i\le m$,有 $0\le p_i,q_i\le n-1$ 和 \(p_i\neq q_i\)

    详细子任务附加限制与分值如下表:

    子任务编号 附加限制 分值
    $1$ 每处景点至多可做两条道路的端点 $7$
    $2$ \(a=1\) $11$
    $3$ \(m=n-1\) $22$
    $4$ \(n\le 2.5\times 10^3,m\le 5\times 10^3\) $24$
    $5$ 没有任何附加限制 $36$

    点此提交