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. |
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: '... |
CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) Editorial |
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 |
Back to search problems