K. Binary Sequence

Codeforces

IDCF10286K

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given a sequence of $n$ bits $a_1$, $\\dots$, $a_n$ (each bit can be either $0$ or $1$). Initially all bits are set to $0$. You are also given $m$ pairs of indices $(i, j)$, which are the possible operations you can apply to the sequence. If you apply an operation $(i, j)$, $a_i$ changes to $1 -a_i$ and $a_j$ to $1 -a_j$. You are also given a target sequence of $n$ bits $b_1$, $\\dots$, $b_n$. Determine if it is possible to obtain $b$ from $a$ by applying the available operations (you can also not change the array at all). Each operation can be applied zero or multiple times, and operations may be appplied in any order. The first line of input contains a single integer, the value of $n$ ($2 <= n <= 10^5$). The following line contains $n$ bits $b_1$, $\\dots$, $b_n$ ($0 <= b_i <= 1$). The next line contains a single integer, the value of $m$ ($1 <= m <= 10^5$). The next $m$ lines each contains two integers $l_i$ and $r_i$, the indexes of an operation ($1 <= l_i < r_i <= n$). No two operations are equal. Output "_Yes_", if it is possible, and "_No_" otherwise. ## Input The first line of input contains a single integer, the value of $n$ ($2 <= n <= 10^5$). The following line contains $n$ bits $b_1$, $\\dots$, $b_n$ ($0 <= b_i <= 1$).The next line contains a single integer, the value of $m$ ($1 <= m <= 10^5$). The next $m$ lines each contains two integers $l_i$ and $r_i$, the indexes of an operation ($1 <= l_i < r_i <= n$). No two operations are equal. ## Output Output "_Yes_", if it is possible, and "_No_" otherwise. [samples]

**Definitions** Let $ G = (V, E) $ be a directed graph with: - $ V = \{1, 2, \dots, N\} $: set of nodes, - $ E = \{e_1, e_2, \dots, e_M\} $: set of directed edges, where $ e_i = (u_i, v_i) $, - $ s_i \in \mathbb{Z} $: score of node $ i $, - Origin node: $ 1 \in V $. Let $ R(G') \subseteq V $ denote the set of nodes reachable from node $ 1 $ in graph $ G' $. **Constraints** 1. $ 1 \le N, M \le 4 \times 10^5 $ 2. $ 1 \le s_i < 2^{31} $ for all $ i \in V $ 3. Initially, $ R(G) = V $ (all nodes reachable from origin) 4. $ 1 \le Q \le 10^5 $ 5. Each query $ q_i \in \{1, \dots, M\} $: remove edge $ e_{q_i} $ **Objective** For each query $ q_i $, let $ G' = G \setminus \{e_{q_i}\} $. Compute the score: $$ \sum_{v \in V \setminus R(G')} s_v $$ That is, the sum of scores of all nodes that become unreachable from node $ 1 $ after removing edge $ e_{q_i} $.

API Response (JSON)

{
  "problem": {
    "name": "K. Binary Sequence",
    "description": {
      "content": "You are given a sequence of $n$ bits $a_1$, $\\\\dots$, $a_n$ (each bit can be either $0$ or $1$). Initially all bits are set to $0$. You are also given $m$ pairs of indices $(i, j)$, which are the poss",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10286K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a sequence of $n$ bits $a_1$, $\\\\dots$, $a_n$ (each bit can be either $0$ or $1$). Initially all bits are set to $0$. You are also given $m$ pairs of indices $(i, j)$, which are the poss...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be a directed graph with:  \n- $ V = \\{1, 2, \\dots, N\\} $: set of nodes,  \n- $ E = \\{e_1, e_2, \\dots, e_M\\} $: set of directed edges, where $ e_i = (u_i, v_i) $,  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments