[CCC 2022 S2] Good Groups

Luogu

IDLGP8396

Time1000ms

Memory128MB

DifficultyP3

并查集2022CCC（加拿大）哈希 hashing

一个班级会被分成 $g$ 个组，每个组有三个人，这种分组方式可能会违反两种规定： 1. 一些学生必须在同一小组； 2. 一些学生必须不在同一小组。现在校长找到了你，问学生违反了多少个规定。 ## Input 第一行一个整数 $x$。接下来 $x$ 行，每行两个学生名字 $name1_1,name1_2$ ，表示这两个学生必须被分配到同一个小组。接下来一个整数 $y$。接下来 $y$ 行，每行两个学生名字 $name2_1,name2_2$ ，表示这两个学生必须不在同一个小组。接下来一个整数 $g$。接下来 $g$ 行，每行三个学生名字 $name3_1,name3_2,name3_3$，表示这三个学生现在被分在一个小组。 ## Output 输出一个整数，表示学生违反了多少个规定。 [samples] ## Background 请注意：这道题是 [CCO 2022 J4 Good Groups](https://www.luogu.com.cn/problem/P8403) 的加强版。管理备注：似乎没有加强。 ## Note ### 样例 2 解释： 1. $\rm A$ 和 $\rm B$ 必须在同一组，这一点违反了。 2. $\rm G$ 和 $\rm L$ 必须在同一组，这一点违反了。 3. $\rm J$ 和 $\rm K$ 必须在同一组，这一点没有违反。 4. $\rm D$ 和 $\rm F$ 必须不在同一组，这一点违反了。 5. $\rm D$ 和 $\rm G$ 必须不在同一组，这一点没有被违反。以上 $5$ 条共违反 $3$ 条，所以输出 $3$。对于 $20\%$ 的数据：$1\le g\le 50$，$1\le x\le 50$，$y=0$。对于另外 $35\%$ 的数据：$1\le g\le 50$，$1\le x\le 50$，$1\le y\le 50$。对于 $100\%$ 的数据：$1\le g\le 10^5$，$1\le x\le 10^5$，$1\le y\le 10^5$。

Samples

Input #1

1
ELODIE CHI
0
2
DWAYNE BEN ANJALI
CHI FRANCOIS ELODIE

Output #1

Input #2

3
A B
G L
J K
2
D F
D G
4
A C G
B D F
E H I
J K L

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[CCC 2022 S2] Good Groups",
    "description": {
      "content": "一个班级会被分成 $g$ 个组，每个组有三个人，这种分组方式可能会违反两种规定： 1. 一些学生必须在同一小组； 2. 一些学生必须不在同一小组。 现在校长找到了你，问学生违反了多少个规定。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8396"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一个班级会被分成 $g$ 个组，每个组有三个人，这种分组方式可能会违反两种规定：\n\n1. 一些学生必须在同一小组；\n2. 一些学生必须不在同一小组。\n\n现在校长找到了你，问学生违反了多少个规定。\n\n## Input\n\n第一行一个整数 $x$。\n\n接下来 $x$ 行，每行两个学生名字 $name1_1,name1_2$ ，表示这两个学生必须被分配到同一个小组。\n\n接下来一个整数 $y$。\n\n接下来 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments