問題一覧 > 教育的問題

No.3576 Mapping Check

レベル : / AI推定難易度 : 189 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 31
作問者 : 👑 p-adic
お気に入りにしたユーザー ProblemId : 9234 / 自分の提出
問題文最終更新日: 2026-06-27 09:11:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 503 (順位表) の他の問題:

Problem Statement

The input gives a non-negative integer $N$ and $N$ pairs of $2$ non-negative integers.

Let $F$ be the set consisting of the given $N$ pairs.

That is, for each positive integer $i$ not exceeding $N$, if we denote the $i$-th given pair by $(s_i,t_i)$, then $F = \{(s_i,t_i) \mid i \in \N \cap [1,N]\} = \{(s_1,t_1), \ldots, (s_N,t_N)\}$.

 

We say that $F$ is a good set if $F$ satisfies the following property:

  • For any elements $(s,t)$ and $(s',t')$ of $F$, if $s = s'$, then $t = t'$.

 

Determine whether $F$ is a good set.

Background

$F$ being a good set means precisely that $F$ is a map. In other words, this problem asks you to determine whether $F$ is a map.

Here is a supplementary note for those who want to know more about maps. (Click to open)

 

First, here is a rough picture. A map is a generalization of a function: it is a concept in which the domain (the set of all values that can be substituted) can be chosen freely, and the values can also be chosen freely and are not limited to numbers. In this problem, we only consider maps whose domain is a subset of the set of all non-negative integers and whose values are non-negative integers.

A map is itself a set, and the elements of a map $f$ are the pairs $(x,f(x))$ as $x$ ranges over the elements of the domain. It may look like a strange set at first glance, but picturing a map in c++ may make it easier to understand.

 

The rough understanding above is sufficient for solving this problem, but here is an explanation for those who want the rigorous formulation of the domain and substitution. When $f$ is a map, the set of all first components (component $1$) $s$ of its elements $(s,t)$,

$\displaystyle \{s \mid \exists t[(s,t) \in f]\} $

is called the domain of $f$, and the set of all second components (component $2$) $t$,

$\displaystyle \{t \mid \exists s[(s,t) \in f]\} $

is called the range of $f$. In a context where a set containing the range is fixed, such a set is called the codomain of $f$.

Once $f$ and an element $s$ of its domain are fixed, the definition of a map implies that there is exactly one $t$ satisfying $(s,t) \in f$, and we denote it by $f(s)$. In this sense, $f(s)$ is defined only when $s$ belongs to the domain of $f$, so the domain of $f$ is exactly the region on which $f(s)$ is defined.

As you can guess from this notation using $()$ and from the term "domain", the concept of a map is used as a set-theoretic generalization of (single-valued) functions. Indeed, if you think of the graph of a function you know, you will be convinced that it satisfies the definition of a map (as the set of all points on the graph).

For example, the set $f = \{(0,3),(1,2),(2,5)\}$ is a map with domain $\{0,1,2\}$, and it satisfies

$\displaystyle \begin{array}{rcl} \displaystyle f(0) &\displaystyle = &\displaystyle 3 \\ \displaystyle f(1) &\displaystyle = &\displaystyle 2 \\ \displaystyle f(2) &\displaystyle = &\displaystyle 5 \end{array} $

.

Input

The input is given from standard input in $1 + N$ lines in the following format:

  • Line $1$ contains $N$.
  • For each positive integer $i$ not exceeding $N$, line $1 + i$ contains $s_i, t_i$ separated by a single-byte space.
$N$
$s_1$ $t_1$
$\vdots$
$s_N$ $t_N$

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $0 \leq N \leq 10^5$.
  • For any positive integer $i$ not exceeding $N$:
    • $s_i$ is an integer satisfying $0 \leq s_i \leq 10^5$.
    • $t_i$ is an integer satisfying $0 \leq t_i \leq 10^5$.

Output

Print Yes if $F$ is a good set, and No otherwise.

Print a newline at the end.

Sample

Sample 1
Input
1
0 1
Output
Yes

$F = \{(0,1)\}$ is a good set.

For those familiar with maps, $F$ is a map with domain $\{0\}$ satisfying $F(0) = 1$.

Sample 2
Input
2
1 0
0 0

As in this case, it may be that $s_0 \leq s_1$ does not hold.

Output
Yes

$F = \{(1,0),(0,0)\}$ is a good set.

For those familiar with maps, $F$ is a map with domain $\{0,1\}$ satisfying $F(0) = F(1) = 0$.

Sample 3
Input
2
0 1
0 2
Output
No

Here, $F = \{(0,1),(0,2)\}$.

Since $(0,1) \in F$, $(0,2) \in F$, and $1 \neq 2$, $F$ is not a good set.

Sample 4
Input
2
0 1
0 1

As in this case, it may be that $(s_0,t_0) \neq (s_1,t_1)$ does not hold.

Output
Yes

$F = \{(0,1),(0,1)\} = \{(0,1)\}$ is the same set as in Sample 1, so it is a good set.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。