K. Kill Bridges

Codeforces

IDCF10088K

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

CodeCraft'16 gives you the opportunity to become a killer(legally!). Subject to the constraint that you are best at your job. So you have to prove yourself. Given an undirected, unweighted, connected graph with N vertices and M edges, you have to add at most K new edges in the graph to minimize the number of bridges. There will be Q queries each with a K. Each query is independent _i.e._ you have to consider the original graph for each query. First line contains three integers N, M and Q(1 ≤ N, Q ≤ 105 and 0 ≤ M ≤ 2 * 105). Next M lines contain u and v denoting an undirected edge between u and v(1 ≤ u, v ≤ N). Next Q lines contain a single integer K(1 ≤ K ≤ M) denoting the maximum number of edges that you can add. For each query output the maximum number of bridges you can kill. Adding the edge removes the existing 2 bridges. ## Input First line contains three integers N, M and Q(1 ≤ N, Q ≤ 105 and 0 ≤ M ≤ 2 * 105). Next M lines contain u and v denoting an undirected edge between u and v(1 ≤ u, v ≤ N). Next Q lines contain a single integer K(1 ≤ K ≤ M) denoting the maximum number of edges that you can add. ## Output For each query output the maximum number of bridges you can kill. [samples] ## Note Adding the edge removes the existing 2 bridges.

**Definitions** Let $ G = (V, E) $ be an undirected, unweighted, connected graph with $ |V| = N $, $ |E| = M $. Let $ B \subseteq E $ be the set of bridges in $ G $. Let $ \mathcal{E} $ be the set of all possible non-existing edges (i.e., $ \binom{V}{2} \setminus E $). **Constraints** 1. $ 1 \le N, Q \le 10^5 $ 2. $ 0 \le M \le 2 \cdot 10^5 $ 3. For each query, $ 1 \le K \le M $ 4. Each query is independent; graph reverts to original before each query. **Objective** For each query with parameter $ K $, determine the **maximum number of bridges that can be eliminated** by adding at most $ K $ edges from $ \mathcal{E} $. Let $ f(K) $ denote the maximum number of bridges removable by adding $ \le K $ edges. Output $ f(K) $ for each query.

API Response (JSON)

{
  "problem": {
    "name": "K. Kill Bridges",
    "description": {
      "content": "CodeCraft'16 gives you the opportunity to become a killer(legally!). Subject to the constraint that you are best at your job. So you have to prove yourself. Given an undirected, unweighted, connected",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10088K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "CodeCraft'16 gives you the opportunity to become a killer(legally!). Subject to the constraint that you are best at your job. So you have to prove yourself.\n\nGiven an undirected, unweighted, connected...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be an undirected, unweighted, connected graph with $ |V| = N $, $ |E| = M $.  \nLet $ B \\subseteq E $ be the set of bridges in $ G $.  \nLet $ \\mathcal{E} $ be the s...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments