Codeforces Round 947 (Div. 1 + Div. 2)

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
1975 Codeforces Round 947 (Div. 1 + Div. 2) FINISHED False 10800 20532263 May 25, 2024, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 2402 ) E Chain Queries PROGRAMMING binary search data structures dfs and similar implementation trees 2100

B'You are given a tree of n vertices numbered from 1 to n . Initially, all vertices are colored white or black. You are asked to perform q queries: After each query, you should answer whether all the black vertices form a chain. That is, there exist two black vertices such that the simple path between them passes through all the black vertices and only the black vertices. Specifically, if there is only one black vertex, they form a chain. If there are no black vertices, they do not form a chain. Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= q t <= q 10^4 ). The description of the test cases follows. The first line of each test case contains two integers n and q ( 1 <= q n,q <= q 2 cdot 10^5 ). The second line of each test case contains n integers c_1,c_2, ldots,c_n ( c_i in { mathtt{0}, mathtt{1} } ) -- the initial color of the vertices. c_i denotes the color of vertex i where mathtt{0} denotes the color white, and mathtt{1} denotes the color black. Then n - 1 lines follow, each line contains two integers x_i and y_i ( 1 <= x_i,y_i <= n ), indicating an edge between vertices x_i and y_i . It is guaranteed that these edges form a tree. The following q lines each contain an integer u_i ( 1 <= u_i <= n ), indicating the color of vertex u_i needs to be toggled. It is guaranteed that the sum of n and q over all test cases respectively does not exceed 2 cdot 10^5 . For each query, output "Yes" if the black vertices form a chain, and output "No" otherwise. You can output "Yes" and "No" in any case (for example, strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive response). In the second test case, the color of the vertices are as follows: The initial tree: The first query toggles the color of vertex 4 : The second query t'...

Tutorials

editorial_zh.pdf

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
263704077 karamkontar E June 2, 2024, 5:46 a.m. OK C# 10 TESTS 73 609 57548800 2100
263703476 karamkontar E June 2, 2024, 5:39 a.m. OK C# 10 TESTS 73 655 57548800 2100
263589554 kbzcz E June 1, 2024, 7:10 a.m. OK C++14 (GCC 6-32) TESTS 73 265 11468800 2100
262914988 Hanoist E May 27, 2024, 5:18 p.m. OK C++14 (GCC 6-32) TESTS 73 265 13107200 2100
262873337 Iceturky E May 27, 2024, 11:43 a.m. OK C++14 (GCC 6-32) TESTS 73 265 25088000 2100
262915221 Hanoist E May 27, 2024, 5:20 p.m. OK C++14 (GCC 6-32) TESTS 73 280 13107200 2100
262943388 MrPython E May 28, 2024, 1:08 a.m. OK C++14 (GCC 6-32) TESTS 73 296 13414400 2100
263589504 kbzcz E June 1, 2024, 7:10 a.m. OK C++14 (GCC 6-32) TESTS 73 311 11468800 2100
263410122 CharlieCai E May 31, 2024, 4:42 a.m. OK C++14 (GCC 6-32) TESTS 73 311 31539200 2100
262856895 Zero_s E May 27, 2024, 9:24 a.m. OK C++14 (GCC 6-32) TESTS 73 327 21913600 2100
263199216 CharlieCai E May 30, 2024, 4:44 a.m. OK C++14 (GCC 6-32) TESTS 73 327 31539200 2100
263246414 UraykevoliQwQ E May 30, 2024, 12:21 p.m. OK C++14 (GCC 6-32) TESTS 73 343 14131200 2100
262715284 purp4ever E May 26, 2024, 2:15 p.m. OK C++17 (GCC 7-32) TESTS 73 296 14131200 2100
262822909 Roman_2007 E May 27, 2024, 4:38 a.m. OK C++17 (GCC 7-32) TESTS 73 312 11776000 2100
263556831 sverma2 E May 31, 2024, 11:34 p.m. OK C++17 (GCC 7-32) TESTS 73 312 14233600 2100
262811807 CoderAbhi27 E May 27, 2024, 1:14 a.m. OK C++17 (GCC 7-32) TESTS 73 327 25292800 2100
263062799 Krispy E May 28, 2024, 8:27 p.m. OK C++17 (GCC 7-32) TESTS 73 327 25497600 2100
262823525 Roman_2007 E May 27, 2024, 4:46 a.m. OK C++17 (GCC 7-32) TESTS 73 343 11776000 2100
262845948 jiraiya_chan E May 27, 2024, 7:50 a.m. OK C++17 (GCC 7-32) TESTS 73 343 14131200 2100
262821123 vanshvyas26 E May 27, 2024, 4:12 a.m. OK C++17 (GCC 7-32) TESTS 73 343 14950400 2100
262809886 SpadeA261 E May 27, 2024, 12:22 a.m. OK C++17 (GCC 7-32) TESTS 73 343 14950400 2100
263161545 shallowai E May 29, 2024, 3:19 p.m. OK C++17 (GCC 7-32) TESTS 73 343 16486400 2100
262844222 N_z__ E May 27, 2024, 7:37 a.m. OK C++20 (GCC 13-64) TESTS 73 187 14745600 2100
262820634 orzdevinwang E May 27, 2024, 4:04 a.m. OK C++20 (GCC 13-64) TESTS 73 249 130048000 2100
262715127 FantasyNumber E May 26, 2024, 2:14 p.m. OK C++20 (GCC 13-64) TESTS 73 250 12595200 2100
262711485 Liuxizai E May 26, 2024, 1:41 p.m. OK C++20 (GCC 13-64) TESTS 73 265 13312000 2100
262824926 aLyingFlat E May 27, 2024, 5:04 a.m. OK C++20 (GCC 13-64) TESTS 73 265 13824000 2100
263158290 Hojstyer E May 29, 2024, 2:49 p.m. OK C++20 (GCC 13-64) TESTS 73 265 14336000 2100
262886037 lizhiqing E May 27, 2024, 1:18 p.m. OK C++20 (GCC 13-64) TESTS 73 265 28364800 2100
262969293 cat_of_Nesraychan E May 28, 2024, 6:45 a.m. OK C++20 (GCC 13-64) TESTS 73 265 28979200 2100
262849639 zhangxiaogao E May 27, 2024, 8:21 a.m. OK C++20 (GCC 13-64) TESTS 73 280 16179200 2100
263422462 void_3 E May 31, 2024, 6:35 a.m. OK C++20 (GCC 13-64) TESTS 73 280 19251200 2100
263445383 nguyenquocthao00 E May 31, 2024, 10:02 a.m. OK Go TESTS 73 609 104140800 2100
263073433 dzhi E May 29, 2024, 12:40 a.m. OK Java 21 TESTS 73 1280 138752000 2100
263073667 dzhi E May 29, 2024, 12:47 a.m. OK Java 21 TESTS 73 1468 138240000 2100
263106904 yvbf E May 29, 2024, 7:54 a.m. OK Java 8 TESTS 73 374 24678400 2100
263685411 leonlian E June 1, 2024, 10:58 p.m. OK Java 8 TESTS 73 874 131788800 2100
262834982 chinatest E May 27, 2024, 6:25 a.m. OK Java 8 TESTS 73 1249 53964800 2100
262951802 Little_Sheep_Yawn E May 28, 2024, 3:41 a.m. OK PyPy 3-64 TESTS 73 593 60928000 2100
263011255 ossau_guildo E May 28, 2024, 12:39 p.m. OK PyPy 3-64 TESTS 73 687 59392000 2100
263060529 gardengnome E May 28, 2024, 7:54 p.m. OK PyPy 3-64 TESTS 73 703 65843200 2100
262848858 accelerate_nju E May 27, 2024, 8:14 a.m. OK PyPy 3-64 TESTS 73 811 69017600 2100
262713660 jgs03177 E May 26, 2024, 2 p.m. OK PyPy 3-64 TESTS 73 858 51200000 2100
262799121 edugong E May 26, 2024, 8:18 p.m. OK PyPy 3-64 TESTS 73 1421 64307200 2100
263112471 EBeason E May 29, 2024, 8:39 a.m. OK PyPy 3-64 TESTS 73 1702 47718400 2100
263190334 Maksim1744 E May 29, 2024, 11:13 p.m. OK Rust 2021 TESTS 73 203 43008000 2100
262932729 andrey.m E May 27, 2024, 8:42 p.m. OK Rust 2021 TESTS 73 389 43724800 2100
262714725 0npata E May 26, 2024, 2:10 p.m. OK Rust 2021 TESTS 73 483 249344000 2100
263068220 PlaceOrientedProgrammer E May 28, 2024, 10:10 p.m. OK Rust 2021 TESTS 73 546 44544000 2100
262796539 camc E May 26, 2024, 7:41 p.m. OK Rust 2021 TESTS 73 546 112128000 2100
262841176 toor E May 27, 2024, 7:14 a.m. OK Rust 2021 TESTS 73 608 73523200 2100
262845414 toor E May 27, 2024, 7:45 a.m. OK Rust 2021 TESTS 73 874 73420800 2100
262841371 toor E May 27, 2024, 7:16 a.m. OK Rust 2021 TESTS 73 968 73420800 2100

remove filters

Back to search problems