Codeforces Round 1040 (Div. 1)

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
2129 Codeforces Round 1040 (Div. 1) FINISHED False 10800 22433123 July 31, 2025, 2:35 p.m.

Problems

Solved
Index
Name
Type
Tags
Community Tag
Rating
( 473 ) E Induced Subgraph Queries PROGRAMMING data structures graphs sortings

You are given an unweighted, undirected graph (G) with (n) nodes and (m) edges. The graph (G) contains no self-loops or multiple edges. We denote the node set of (G) as (V). For any node subset (V' \subseteq V), the corresponding induced subgraph, denoted by (GV'), is defined as follows: (GV') is the graph whose node set is (V'), and whose edge set consists of all edges in (G) with both endpoints in (V'). Your task is to answer (q) queries. Each query provides three integers (l), (r), and (k). Denoting (V'=\{l,l+1,\ldots,r\}), you need to find the (k)-th smallest value among (f(l,GV')), (f(l+1,GV')), (\ldots) , (f(r,GV')) (i.e., the (k)-th value in increasing order; repeated values are counted multiple times). Here, (f(u,GV')=\bigoplus_{(u,v)\in GV'}v). In other words, it is the bitwise XOR value of the labels of all adjacent nodes of node (u) in graph (GV'). You might want to read the notes for a better understanding. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 1.5 \cdot 10^4)). The description of the test cases follows. Each test case begins with two integers (n) and (m) ((2 \leq n \leq 1.5 \cdot 10^5), (1 \leq m \leq 1.5 \cdot 10^5)) — the number of nodes and edges, respectively. The next (m) lines each contain two integers (u_i) and (v_i) ((1 \leq u_i, v_i \leq n), (u_i \neq v_i)), representing an undirected edge between nodes (u_i) and (v_i). The next line contains a single integer (q) ((1 \leq q \leq 1.5 \cdot 10^5)) — the number of queries. Each of the next (q) lines contains three integers (l), (r), and (k) ((1 \leq l \leq r \leq n), (1 \le k \le r-l+1)), defining a query about the induced subgraph (G\{l,\ldots,r\}). It is guaranteed that the graph contains no self-loops or multip

Tutorials

Codeforces Round 1040 (Div. 1, Div. 2) Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
331901189 Flamire E Aug. 1, 2025, 5:04 a.m. OK C++17 (GCC 7-32) TESTS 100 1749 21708800
331827672 Crystally E July 31, 2025, 4:23 p.m. OK C++17 (GCC 7-32) TESTS 100 2046 88371200
331852017 loveye E July 31, 2025, 5:26 p.m. OK C++17 (GCC 7-32) TESTS 100 2062 8908800
331901375 awu E Aug. 1, 2025, 5:07 a.m. OK C++17 (GCC 7-32) TESTS 100 2531 9625600
331896132 lichenghan E Aug. 1, 2025, 3:57 a.m. OK C++17 (GCC 7-32) TESTS 100 2984 11878400
331819307 jiangbowen E July 31, 2025, 4:05 p.m. OK C++17 (GCC 7-32) TESTS 100 2999 10854400
331855518 alireza_kaviani E July 31, 2025, 5:34 p.m. OK C++17 (GCC 7-32) TESTS 100 3077 26419200
331851950 Flamire E July 31, 2025, 5:25 p.m. OK C++17 (GCC 7-32) TESTS 100 3343 24678400
331818285 Um_nik E July 31, 2025, 4:03 p.m. OK C++17 (GCC 7-32) TESTS 100 3515 132505600
331900919 Flamire E Aug. 1, 2025, 5:01 a.m. OK C++17 (GCC 7-32) TESTS 100 3577 24780800
331824756 strapple E July 31, 2025, 4:16 p.m. OK C++20 (GCC 13-64) TESTS 100 1406 95027200
331872905 Anonymous_Noob E July 31, 2025, 9:52 p.m. OK C++20 (GCC 13-64) TESTS 100 1421 11571200
331872648 Anonymous_Noob E July 31, 2025, 9:48 p.m. OK C++20 (GCC 13-64) TESTS 100 1609 11673600
331872385 Anonymous_Noob E July 31, 2025, 9:43 p.m. OK C++20 (GCC 13-64) TESTS 100 1640 13004800
331895945 tiger2005 E Aug. 1, 2025, 3:55 a.m. OK C++20 (GCC 13-64) TESTS 100 1640 13516800
331872452 Anonymous_Noob E July 31, 2025, 9:44 p.m. OK C++20 (GCC 13-64) TESTS 100 1655 13004800
331874575 dorijanlendvaj E July 31, 2025, 10:32 p.m. OK C++20 (GCC 13-64) TESTS 100 1655 42188800
331830778 Milkcat2009 E July 31, 2025, 4:30 p.m. OK C++20 (GCC 13-64) TESTS 100 1733 80384000
331829628 Gold14526 E July 31, 2025, 4:27 p.m. OK C++20 (GCC 13-64) TESTS 100 1734 13107200
331855231 dorijanlendvaj E July 31, 2025, 5:33 p.m. OK C++20 (GCC 13-64) TESTS 100 1812 42086400
331796557 maspy E July 31, 2025, 3:27 p.m. OK C++23 (GCC 14-64, msys2) TESTS 100 1093 28876800
331779636 YCY_love_little09 E July 31, 2025, 3:06 p.m. OK C++23 (GCC 14-64, msys2) TESTS 100 1577 14950400
331888740 toam E Aug. 1, 2025, 2:33 a.m. OK C++23 (GCC 14-64, msys2) TESTS 100 1640 11059200
331888655 toam E Aug. 1, 2025, 2:31 a.m. OK C++23 (GCC 14-64, msys2) TESTS 100 1671 10956800
331869004 PinkieRabbit E July 31, 2025, 8:46 p.m. OK C++23 (GCC 14-64, msys2) TESTS 100 1718 10649600
331829777 Nachia E July 31, 2025, 4:27 p.m. OK C++23 (GCC 14-64, msys2) TESTS 100 1765 8908800
331871461 tin.le2 E July 31, 2025, 9:26 p.m. OK C++23 (GCC 14-64, msys2) TESTS 100 1780 57856000
331805911 ecnerwala E July 31, 2025, 3:42 p.m. OK C++23 (GCC 14-64, msys2) TESTS 100 1781 9011200
331888810 toam E Aug. 1, 2025, 2:33 a.m. OK C++23 (GCC 14-64, msys2) TESTS 100 1827 11059200
331866222 platter E July 31, 2025, 8:16 p.m. OK C++23 (GCC 14-64, msys2) TESTS 100 1858 26931200
331877055 sansen E July 31, 2025, 11:43 p.m. OK Rust 2021 TESTS 100 2624 23552000
331876230 sansen E July 31, 2025, 11:20 p.m. OK Rust 2021 TESTS 100 2686 23449600
331903338 Ming_Xu E Aug. 1, 2025, 5:31 a.m. OK Rust 2021 TESTS 100 3124 42291200
331903399 Ming_Xu E Aug. 1, 2025, 5:32 a.m. OK Rust 2021 TESTS 100 3186 42393600
331832695 Egor E July 31, 2025, 4:34 p.m. OK Rust 2021 TESTS 100 3952 24268800
331899809 Sugar_fan E Aug. 1, 2025, 4:46 a.m. OK Rust 2021 TESTS 100 4827 23552000

remove filters

Back to search problems