A1306 | [COCI-2013_2014-contest5]#3 LADICE
来源COCI
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
Mirko has N items (labeled with numbers from 1 to N) and L drawers (labeled with numbers from 1 to L). All items are currently scattered throughout his room, so he decided to clean them up. Each drawer can contain one item, and in order to make it easier for Mirko to find them later, he has determined in advance exactly two drawers (Ai and Bi ) for each item i.
Mirko stores the items in order from 1 to N using the first rule he can apply:
1. If the drawer Ai is empty, he stores the item i in that drawer
2. If the drawer Bi is empty, he stores the item i in that drawer
3. Try to move the item from Ai to its other drawer; if that one's filled too, try moving that item to its other drawer, and so on until you either succeed or get back to a previously seen drawer. In case of success, store the item i in the drawer Ai . In case of failure, continue to next rule.
4. Try moving the item from Bi to its other drawer; if that one's filled too, try moving that item to its other drawer, and so on until you either succeed or get back to a previously seen drawer. In case of success, store the item i in the drawer Bi . In case of failure, continue to next rule.
5. Give up and throw away the item i.
For given pairs of drawers for each item, determine which items will be stored and which will be thrown away.
Mirko stores the items in order from 1 to N using the first rule he can apply:
1. If the drawer Ai is empty, he stores the item i in that drawer
2. If the drawer Bi is empty, he stores the item i in that drawer
3. Try to move the item from Ai to its other drawer; if that one's filled too, try moving that item to its other drawer, and so on until you either succeed or get back to a previously seen drawer. In case of success, store the item i in the drawer Ai . In case of failure, continue to next rule.
4. Try moving the item from Bi to its other drawer; if that one's filled too, try moving that item to its other drawer, and so on until you either succeed or get back to a previously seen drawer. In case of success, store the item i in the drawer Bi . In case of failure, continue to next rule.
5. Give up and throw away the item i.
For given pairs of drawers for each item, determine which items will be stored and which will be thrown away.
输入格式
The first line of input consists of two integers, N and L (1 ≤ N, L ≤ 300 000), the number of items and the number of drawers.
Each of the following N lines contains two integers: Ai and Bi (1 ≤ Ai and Bi ≤ L), pair of drawers corresponding to the item i. The numbers Ai and Bi will be different.
Each of the following N lines contains two integers: Ai and Bi (1 ≤ Ai and Bi ≤ L), pair of drawers corresponding to the item i. The numbers Ai and Bi will be different.
输出格式
For each item, respectively, output where it ends up.
In case the item is stored successfully, output "LADICA" (without quotes, Croatian word for drawer).
In case the item is thrown away, output "SMECE" (without quotes, Croatian word for trash).
In case the item is stored successfully, output "LADICA" (without quotes, Croatian word for drawer).
In case the item is thrown away, output "SMECE" (without quotes, Croatian word for trash).
输入输出样例
输入 #1
5 3 1 2 1 3 1 2 1 3 1 2
输出 #1
LADICA LADICA LADICA SMECE SMECE
输入 #2
9 10 1 2 3 4 5 6 7 8 9 10 2 3 1 5 8 2 7 9
输出 #2
LADICA LADICA LADICA LADICA LADICA LADICA LADICA LADICA LADICA
In test cases worth 50% of total points, both N and L will be lesser than 2000.
Clarification of the first example: The first item goes to drawer 1 by rule 1). The second item goes to
drawer 3 by rule 2). The third item goes to drawer 2 by rule 2).
For the fourth and fifth item, both drawers are already taken and cannot be emptied.
Clarification of the second example: The first six items go into drawers 1, 3, 5, 7, 9, 2 (respectively),
by rule 1). For the seventh item, applying the rule 3), we try to move the item in drawer 1 to drawer 2,
the item in drawer 2 to drawer 3, the item in drawer 3 to drawer 4, which we succeed because the
drawer is empty.
The eighth item goes to drawer 8 which was empty from the beginning.
For the ninth item, applying the rule 3), we try to move the item in drawer 7 to drawer 8, the item in
drawer 8 to drawer 2, the item in drawer 2 to drawer 1, the item in drawer 1 to drawer 5, the item in
drawer 5 to drawer 6, which we succeed because the drawer is empty.
Clarification of the first example: The first item goes to drawer 1 by rule 1). The second item goes to
drawer 3 by rule 2). The third item goes to drawer 2 by rule 2).
For the fourth and fifth item, both drawers are already taken and cannot be emptied.
Clarification of the second example: The first six items go into drawers 1, 3, 5, 7, 9, 2 (respectively),
by rule 1). For the seventh item, applying the rule 3), we try to move the item in drawer 1 to drawer 2,
the item in drawer 2 to drawer 3, the item in drawer 3 to drawer 4, which we succeed because the
drawer is empty.
The eighth item goes to drawer 8 which was empty from the beginning.
For the ninth item, applying the rule 3), we try to move the item in drawer 7 to drawer 8, the item in
drawer 8 to drawer 2, the item in drawer 2 to drawer 1, the item in drawer 1 to drawer 5, the item in
drawer 5 to drawer 6, which we succeed because the drawer is empty.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted