Codeforces Round 873 (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
1827 Codeforces Round 873 (Div. 1) FINISHED False 7200 53191463 May 14, 2023, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 435 ) E Bus Routes PROGRAMMING binary search constructive algorithms dfs and similar greedy trees 3400

B'There is a country consisting of n cities and n - 1 bidirectional roads connecting them such that we can travel between any two cities using these roads. In other words, these cities and roads form a tree. There are m bus routes connecting the cities together. A bus route between city x and city y allows you to travel between any two cities in the simple path between x and y with this route. Determine if for every pair of cities u and v , you can travel from u to v using at most two bus routes. Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= t <= 10^4 ). The description of the test cases follows. The first line of each test case contains two integers n and m ( 2 <= n <= 5 cdot 10^5, 0 <= m <= 5 cdot 10^5 ) -- the number of cities and the number of bus routes. Then n - 1 lines follow. Each line contains two integers u and v denoting a road connecting city u and city v ( 1 <= u, v <= n, u neq v ). It is guaranteed that these cities and roads form a tree. Then m lines follow. Each line contains two integers x and y denoting a bus route between city x and city y ( 1 <= x, y <= n ). It is guaranteed that the sum of n over all test cases does not exceed 5 cdot 10^5 and the sum of m over all test cases does not exceed 5 cdot 10^5 . For each test case, output "YES" if you can travel between any pair of cities using at most two bus routes. Otherwise, output "NO". In the next line, output two cities x and y ( 1 <= x, y <= n ) such that it is impossible to reach city y from city x using at most two bus routes. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses. Here are the graphs of test case'...

Tutorials

Codeforces Round #873 (Div. 1 & 2) Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
205916357 rainboy E May 14, 2023, 7:24 p.m. OK GNU C11 TESTS 172 795 58572800 3400
206454296 Iridescent2020 E May 19, 2023, 1:56 p.m. OK GNU C++14 TESTS 172 1122 81510400 3400
206453006 Iridescent2020 E May 19, 2023, 1:43 p.m. OK GNU C++14 TESTS 172 1169 81510400 3400
206166111 hgzxwzf E May 17, 2023, 2:39 a.m. OK GNU C++14 TESTS 172 1216 148275200 3400
206166014 hgzxwzf E May 17, 2023, 2:36 a.m. OK GNU C++14 TESTS 172 1216 196300800 3400
206344727 mdshakib2003. E May 18, 2023, 1:21 p.m. OK GNU C++14 TESTS 172 1216 196300800 3400
206069019 luogu_bot2 E May 16, 2023, 9:37 a.m. OK GNU C++14 TESTS 172 1263 196812800 3400
206088097 realFZzzz E May 16, 2023, 12:45 p.m. OK GNU C++14 TESTS 172 1310 60108800 3400
206151755 bekzhan29 E May 16, 2023, 7:50 p.m. OK GNU C++14 TESTS 172 1310 151654400 3400
206353175 cyh_toby E May 18, 2023, 2:36 p.m. OK GNU C++14 TESTS 172 1403 95027200 3400
206353141 cyh_toby E May 18, 2023, 2:35 p.m. OK GNU C++14 TESTS 172 1435 95027200 3400
206046306 Hritik12 E May 16, 2023, 4:44 a.m. OK GNU C++17 TESTS 172 1060 83353600 3400
206215140 lukamosiashvili E May 17, 2023, 1:17 p.m. OK GNU C++17 TESTS 172 1325 136192000 3400
206321186 aziz_kamri E May 18, 2023, 9:39 a.m. OK GNU C++17 TESTS 172 1372 97894400 3400
205923166 Sputnik12 E May 14, 2023, 8:59 p.m. OK GNU C++17 TESTS 172 1388 70348800 3400
206576873 chengcheng5677 E May 20, 2023, 12:36 a.m. OK GNU C++17 TESTS 172 1403 97894400 3400
206315152 ikaurov E May 18, 2023, 8:39 a.m. OK GNU C++17 TESTS 172 1419 111206400 3400
206050292 Deep_Kevin E May 16, 2023, 5:46 a.m. OK GNU C++17 TESTS 172 1481 103424000 3400
206216019 lukamosiashvili E May 17, 2023, 1:24 p.m. OK GNU C++17 TESTS 172 1482 136192000 3400
206360202 AShRaY3414 E May 18, 2023, 3:40 p.m. OK GNU C++17 TESTS 172 1668 124928000 3400
205925924 nostalgic_knnani E May 14, 2023, 10:03 p.m. OK GNU C++17 TESTS 172 1747 124928000 3400
205906136 noimi E May 14, 2023, 5:37 p.m. OK GNU C++17 (64) TESTS 172 950 219750400 3400
206053759 Kubic E May 16, 2023, 6:34 a.m. OK GNU C++17 (64) TESTS 172 966 149401600 3400
206053621 Kubic E May 16, 2023, 6:33 a.m. OK GNU C++17 (64) TESTS 172 967 149299200 3400
206053801 Kubic E May 16, 2023, 6:35 a.m. OK GNU C++17 (64) TESTS 172 967 149401600 3400
206045771 Xylenox E May 16, 2023, 4:35 a.m. OK GNU C++17 (64) TESTS 172 1045 139161600 3400
206038888 orzdevinwang E May 16, 2023, 2 a.m. OK GNU C++17 (64) TESTS 172 1045 340070400 3400
206395935 ExplodingKonjac E May 19, 2023, 2:02 a.m. OK GNU C++17 (64) TESTS 172 1091 190464000 3400
205940356 YeongTree E May 15, 2023, 4:31 a.m. OK GNU C++17 (64) TESTS 172 1106 162508800 3400
206056184 BeyondHeaven E May 16, 2023, 7:06 a.m. OK GNU C++17 (64) TESTS 172 1138 106188800 3400
205960274 Sana E May 15, 2023, 9:03 a.m. OK GNU C++17 (64) TESTS 172 1138 138035200 3400
206003417 remakegpt E May 15, 2023, 3:34 p.m. OK GNU C++20 (64) TESTS 172 608 123494400 3400
206009994 srinija_chowdary9 E May 15, 2023, 4:42 p.m. OK GNU C++20 (64) TESTS 172 608 123494400 3400
206317341 soudhamini_2000031088 E May 18, 2023, 9:01 a.m. OK GNU C++20 (64) TESTS 172 623 123494400 3400
206316043 2000030958 E May 18, 2023, 8:47 a.m. OK GNU C++20 (64) TESTS 172 623 123494400 3400
206319125 2000031264 E May 18, 2023, 9:18 a.m. OK GNU C++20 (64) TESTS 172 623 123494400 3400
205893207 maroonrk E May 14, 2023, 4:06 p.m. OK GNU C++20 (64) TESTS 172 795 114790400 3400
206350432 luogu_bot1 E May 18, 2023, 2:12 p.m. OK GNU C++20 (64) TESTS 172 920 114073600 3400
205894529 ecnerwala E May 14, 2023, 4:10 p.m. OK GNU C++20 (64) TESTS 172 950 109772800 3400
206350226 limaopipi2022 E May 18, 2023, 2:10 p.m. OK GNU C++20 (64) TESTS 172 982 114073600 3400
205974174 jeroenodb E May 15, 2023, 11:33 a.m. OK GNU C++20 (64) TESTS 172 1044 81305600 3400

remove filters

Back to search problems