CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)

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
1870 CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) FINISHED False 8100 42132263 Sept. 18, 2023, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 88 ) H Standard Graph Problem PROGRAMMING data structures graphs greedy trees

B'You are given a weighted directed graph with n vertices and m edges. Each vertex in the graph can be either highlighted or normal. Initially, all vertices are normal. The cost of the graph is defined as the minimum sum of edge weights that need to be selected so that from each normal vertex one can reach at least one highlighted vertex using the selected edges only. If it is not possible to select the edges, the cost is -1 instead. Your task is to compute the cost of the graph after each of the q queries. The queries can be of two types: Output the cost of the graph after each of the q queries. The first line contains three integers n , m , and q ( 3 <= n <= 2 cdot 10^5, 1 <= m, q <= 2 cdot 10^5 ) -- the number of vertices in the graph, the number of edges, and the number of queries. The next m lines contain the edges of the graph, one edge per line. The i -th line contains three integers u_i , v_i , and c_i ( 1 <= q u_i, v_i <= q n, u_i ne v_i, 1 <= q c_i <= q 10^6 ) -- the endpoints of the i -th edge (from u_i to v_i ) and its weight ( c_i ). The next q lines contain the queries, one query per line. The i -th line contains + ;v_i , if it is a query of the first type, and - ;v_i , if it is a query of the second type ( 1 <= q v_i <= q n ). Output q numbers. The i -th number is the cost of the graph after the first i queries. In the first test: '...

Tutorials

CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
223927899 harsh1224 H Sept. 18, 2023, 6:07 p.m. OK GNU C++14 TESTS 34 1216 219136000
223954109 ok777777788 H Sept. 18, 2023, 9:09 p.m. OK GNU C++17 TESTS 34 451 85094400
223954883 amiya H Sept. 18, 2023, 9:23 p.m. OK GNU C++17 (64) TESTS 34 966 88576000
223971766 cnnfls_csy H Sept. 19, 2023, 3:18 a.m. OK GNU C++20 (64) TESTS 34 545 69017600
223950206 ecnerwala H Sept. 18, 2023, 8:10 p.m. OK GNU C++20 (64) TESTS 34 592 70656000
223977132 Hritik12 H Sept. 19, 2023, 4:47 a.m. OK GNU C++20 (64) TESTS 34 623 70656000
223912817 emptyhope H Sept. 18, 2023, 4:36 p.m. OK GNU C++20 (64) TESTS 34 1184 130764800
223918470 yosupo H Sept. 18, 2023, 4:48 p.m. OK GNU C++20 (64) TESTS 34 1185 70041600

remove filters

Back to search problems