[COCI 2021/2022 #5] Usmjeravanje

Luogu
IDLGP8328
Time1000ms
Memory512MB
DifficultyP6
2021Special JudgeCOCI(克罗地亚)
永无岛有两条河流。每条河流沿岸分布有若干个城市,其中城市数量分别为 $a,b$。 对于位于同一条河流沿岸的 $i,j$ 两个城市,如果 $i \lt j$,那么可以通过水路从城市 $i$ 到城市 $j$。 永无岛的居民们已经决定修建 $m$ 条连接第一条河流的城市 $x_i$ 和第二条河流的城市 $y_i$ 的单向航线,但方向有待商榷。 当两个城市之间可以通过水路或航线互相到达时,则称它们是连通的。在所有的城市中,存在若干个城市集合,使得集合中没有任何一对城市是连通的。请为每条航线选择一个方向,使得所有集合中包含元素最多的集合元素个数最少。 ## Input 第一行两个正整数 $a,b$。 第二行一个正整数 $m$。 接下来的 $m$ 行,每行两个正整数 $x_i,y_i$,表示一条连接第一条河流的城市 $x_i$ 和第二条河流的城市 $y_i$ 的单向航线。数据保证没有重复的无序数对 $(x_i,y_i)$ 出现。 ## Output 第一行一个正整数,表示最大集合元素个数的最小值。 第二行 $m$ 个整数 $0$ 或 $1$。其中 $0$ 表示方向从第一条河流的城市 $x_i$ 到第二条河流的城市 $y_i$,$1$ 则相反。 如果有多种符合题意的方案,输出任意一种。 [samples] ## Note **【样例 1 解释】** 最优的方案可以使得每对城市都连通,因此答案为 $1$。 **【数据规模与约定】** **本题采用捆绑测试。** - Subtask 1(20 pts):$1 \le a,b,m \le 15$。 - Subtask 2(30 pts):$1 \le a,b \le 1000$。 - Subtask 3(60 pts):无特殊限制。 对于 $100\%$ 的数据,$1 \le a,b,m \le 2 \times 10^5$,$1 \le x_i \le a$,$1 \le y_i \le b$。 **【说明】** 本题采用自行编写的 [Special Judge](https://www.luogu.com.cn/paste/uv2vgxxa)。如果对此有疑问或想要 hack,请[私信编写者](https://www.luogu.com.cn/chat?uid=137367)或发帖。 **【来源】[COCI 2021-2022#5](https://hsin.hr/coci/contest5_tasks.pdf) Task 5 Usmjeravanje。**
Samples
Input #1
5 3
4
1 2
2 3
3 1
5 3
Output #1
1
1 1 0 0
Input #2
6 6
4
1 2
3 2
4 3
5 6
Output #2
9
1 0 1 1
Input #3
8 7
7
1 3
2 1
3 4
5 6
6 5
6 7
8 7
Output #3
5
1 0 1 1 0 1 0
API Response (JSON)
{
  "problem": {
    "name": "[COCI 2021/2022 #5] Usmjeravanje",
    "description": {
      "content": "永无岛有两条河流。每条河流沿岸分布有若干个城市,其中城市数量分别为 $a,b$。 对于位于同一条河流沿岸的 $i,j$ 两个城市,如果 $i \\lt j$,那么可以通过水路从城市 $i$ 到城市 $j$。 永无岛的居民们已经决定修建 $m$ 条连接第一条河流的城市 $x_i$ 和第二条河流的城市 $y_i$ 的单向航线,但方向有待商榷。 当两个城市之间可以通过水路或航线互相到达时,则称它们是",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8328"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "永无岛有两条河流。每条河流沿岸分布有若干个城市,其中城市数量分别为 $a,b$。\n\n对于位于同一条河流沿岸的 $i,j$ 两个城市,如果 $i \\lt j$,那么可以通过水路从城市 $i$ 到城市 $j$。\n\n永无岛的居民们已经决定修建 $m$ 条连接第一条河流的城市 $x_i$ 和第二条河流的城市 $y_i$ 的单向航线,但方向有待商榷。\n\n当两个城市之间可以通过水路或航线互相到达时,则称它们是...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments