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 |
---|---|---|---|---|---|---|
960 | Divide by Zero 2018 and Codeforces Round 474 (Div. 1 + Div. 2, combined) | FINISHED | False | 9000 | 208706099 | April 7, 2018, 4:05 p.m. |
Solved$ |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
---|---|---|---|---|---|---|
( 1955 ) | E | Alternating Tree | PROGRAMMING | combinatorics dfs and similar divide and conquer dp probabilities trees | 2200 |
B'Given a tree with n nodes numbered from 1 to n . Each node i has an associated value V_i . If the simple path from u_1 to u_m consists of m nodes namely u_1 rightarrow u_2 rightarrow u_3 rightarrow ... u_{m-1} rightarrow u_{m} , then its alternating function A(u_{1},u_{m}) is defined as A(u_{1},u_{m}) = sum limits_{i=1}^{m} (-1)^{i+1} cdot V_{u_{i}} . A path can also have 0 edges, i.e. u_{1}=u_{m} . Compute the sum of alternating functions of all unique simple paths. Note that the paths are directed: two paths are considered different if the starting vertices differ or the ending vertices differ. The answer may be large so compute it modulo 10^{9}+7 . The first line contains an integer n (2 <= q n <= q 2 cdot10^{5} ) -- the number of vertices in the tree. The second line contains n space-separated integers V_1, V_2, ldots, V_n ( -10^9 <= q V_i <= q 10^9 ) -- values of the nodes. The next n-1 lines each contain two space-separated integers u and v (1 <= q u, v <= q xe2 x80 x89n, u neq v) denoting an edge between vertices u and v . It is guaranteed that the given graph is a tree. Print the total sum of alternating functions of all unique simple paths modulo 10^{9}+7 . Consider the first example. A simple path from node 1 to node 2 : 1 rightarrow 2 has alternating function equal to A(1,2) = 1 cdot (-4)+(-1) cdot 1 = -5 . A simple path from node 1 to node 3 : 1 rightarrow 3 has alternating function equal to A(1,3) = 1 cdot (-4)+(-1) cdot 5 = -9 . A simple path from node 2 to node 4 : 2 rightarrow 1 rightarrow 4 has alternating function A(2,4) = 1 cdot (1)+(-1) cdot (-4)+1 cdot (-2) = 3 . A simple path from node 1 to node 1 has a single node 1 , so A(1,1) = 1 cdot (-4) = -4 . Similarly, A(2, 1) = 5 , A(3, 1) ='... |
Divide by Zero 2018 and Codeforces Round #474 (Div. 1 + Div. 2, combined) Editorial |
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
---|---|---|---|---|---|---|---|---|---|---|---|
69887460 | hos.lyric | E | Jan. 31, 2020, 8:45 a.m. | OK | D | TESTS | 96 | 607 | 66457600 | 2200 | |
38063914 | admire.japan | E | May 9, 2018, 7:26 a.m. | OK | D | TESTS | 96 | 655 | 78950400 | 2200 | |
39822881 | 1668 | E | July 1, 2018, 1:47 p.m. | OK | FPC | TESTS | 96 | 249 | 29696000 | 2200 | |
39820645 | OIer_gg | E | July 1, 2018, 12:05 p.m. | OK | FPC | TESTS | 96 | 265 | 37683200 | 2200 | |
38603196 | tswdfop157 | E | May 25, 2018, 7:48 a.m. | OK | GNU C++ | TESTS | 96 | 93 | 25395200 | 2200 | |
38603185 | tswdfop157 | E | May 25, 2018, 7:47 a.m. | OK | GNU C++ | TESTS | 96 | 108 | 25395200 | 2200 | |
40932487 | ReaLNero1 | E | July 30, 2018, 1:50 a.m. | OK | GNU C++ | TESTS | 96 | 109 | 25395200 | 2200 | |
39035763 | redbag | E | June 8, 2018, 4:15 a.m. | OK | GNU C++ | TESTS | 96 | 124 | 40038400 | 2200 | |
37461744 | lcr | E | April 19, 2018, 12:44 p.m. | OK | GNU C++ | TESTS | 96 | 155 | 27545600 | 2200 | |
39785173 | ilnil | E | June 30, 2018, 1:24 a.m. | OK | GNU C++ | TESTS | 96 | 156 | 59801600 | 2200 | |
38603110 | tswdfop157 | E | May 25, 2018, 7:42 a.m. | OK | GNU C++ | TESTS | 96 | 171 | 25395200 | 2200 | |
38421376 | ILLENIUM | E | May 19, 2018, 7:28 a.m. | OK | GNU C++ | TESTS | 96 | 171 | 28876800 | 2200 | |
37262369 | ibuki_suika | E | April 13, 2018, 12:33 a.m. | OK | GNU C++ | TESTS | 96 | 171 | 31334400 | 2200 | |
39855414 | Administratom | E | July 2, 2018, 2:55 a.m. | OK | GNU C++ | TESTS | 96 | 171 | 52838400 | 2200 | |
51377257 | luogu_bot4 | E | March 16, 2019, 2:37 p.m. | OK | GNU C++11 | TESTS | 96 | 78 | 23244800 | 2200 | |
48270474 | fwat | E | Jan. 12, 2019, 1:33 a.m. | OK | GNU C++11 | TESTS | 96 | 93 | 44032000 | 2200 | |
46422897 | LJZ_C | E | Nov. 30, 2018, 11:48 p.m. | OK | GNU C++11 | TESTS | 96 | 108 | 23347200 | 2200 | |
63700268 | luogu_bot5 | E | Oct. 29, 2019, 7:05 a.m. | OK | GNU C++11 | TESTS | 96 | 124 | 16076800 | 2200 | |
46536805 | luogu_bot1 | E | Dec. 3, 2018, 9:30 a.m. | OK | GNU C++11 | TESTS | 96 | 124 | 21606400 | 2200 | |
37107323 | chenyx2001 | E | April 8, 2018, 6:33 p.m. | OK | GNU C++11 | TESTS | 96 | 124 | 26112000 | 2200 | |
63375905 | 910306264 | E | Oct. 25, 2019, 11:01 a.m. | OK | GNU C++11 | TESTS | 96 | 124 | 27750400 | 2200 | |
37124747 | mengbierr | E | April 9, 2018, 2:43 p.m. | OK | GNU C++11 | TESTS | 96 | 124 | 28364800 | 2200 | |
46389195 | vjudge5 | E | Nov. 30, 2018, 3:50 a.m. | OK | GNU C++11 | TESTS | 96 | 124 | 40857600 | 2200 | |
50224642 | vjudge4 | E | Feb. 20, 2019, 6:47 a.m. | OK | GNU C++11 | TESTS | 96 | 124 | 105779200 | 2200 | |
50224802 | vjudge2 | E | Feb. 20, 2019, 6:52 a.m. | OK | GNU C++14 | TESTS | 96 | 202 | 34201600 | 2200 | |
37100473 | chenyanbo | E | April 8, 2018, 1:40 p.m. | OK | GNU C++14 | TESTS | 96 | 218 | 17920000 | 2200 | |
64173839 | vito1036 | E | Nov. 3, 2019, 7:46 p.m. | OK | GNU C++14 | TESTS | 96 | 218 | 21094400 | 2200 | |
43098892 | zhoujundong | E | Sept. 20, 2018, 3:15 a.m. | OK | GNU C++14 | TESTS | 96 | 218 | 24064000 | 2200 | |
62452692 | Nson | E | Oct. 13, 2019, 5:02 a.m. | OK | GNU C++14 | TESTS | 96 | 218 | 28979200 | 2200 | |
62452431 | Nson | E | Oct. 13, 2019, 4:55 a.m. | OK | GNU C++14 | TESTS | 96 | 218 | 33792000 | 2200 | |
62452661 | Nson | E | Oct. 13, 2019, 5:02 a.m. | OK | GNU C++14 | TESTS | 96 | 233 | 28979200 | 2200 | |
57368382 | yan-zp | E | July 20, 2019, 9:56 a.m. | OK | GNU C++14 | TESTS | 96 | 233 | 29081600 | 2200 | |
37079912 | natsugiri | E | April 7, 2018, 7:46 p.m. | OK | GNU C++14 | TESTS | 96 | 234 | 15052800 | 2200 | |
37243587 | BanFcc | E | April 12, 2018, 9 a.m. | OK | GNU C++14 | TESTS | 96 | 234 | 40140800 | 2200 | |
44572058 | orzcyand1317 | E | Oct. 20, 2018, 5:21 a.m. | OK | GNU C++17 | TESTS | 96 | 78 | 23347200 | 2200 | |
44572125 | orzcyand1317 | E | Oct. 20, 2018, 5:22 a.m. | OK | GNU C++17 | TESTS | 96 | 93 | 23347200 | 2200 | |
46422901 | vjudge2 | E | Nov. 30, 2018, 11:49 p.m. | OK | GNU C++17 | TESTS | 96 | 108 | 23347200 | 2200 | |
45175841 | ivan100sic | E | Nov. 1, 2018, 2:41 p.m. | OK | GNU C++17 | TESTS | 96 | 233 | 44236800 | 2200 | |
59595852 | Kuroni | E | Aug. 28, 2019, 1:35 a.m. | OK | GNU C++17 | TESTS | 96 | 248 | 38604800 | 2200 | |
39283191 | zoomswk | E | June 16, 2018, 9:10 a.m. | OK | GNU C++17 | TESTS | 96 | 249 | 27340800 | 2200 | |
69648807 | zzynb | E | Jan. 28, 2020, 3:44 a.m. | OK | GNU C++17 | TESTS | 96 | 249 | 27443200 | 2200 | |
48876527 | vjudge1 | E | Jan. 24, 2019, 8:26 a.m. | OK | GNU C++17 | TESTS | 96 | 249 | 37888000 | 2200 | |
54905783 | sudoBug | E | June 1, 2019, 8:44 a.m. | OK | GNU C++17 | TESTS | 96 | 265 | 21811200 | 2200 | |
37066048 | ko_osaga | E | April 7, 2018, 4:53 p.m. | OK | GNU C++17 | TESTS | 96 | 265 | 22732800 | 2200 | |
37065735 | uwi | E | April 7, 2018, 4:51 p.m. | OK | Java 8 | TESTS | 96 | 326 | 28262400 | 2200 | |
37852752 | donli | E | May 3, 2018, 3:38 a.m. | OK | Java 8 | TESTS | 96 | 374 | 44032000 | 2200 | |
46527204 | kessido | E | Dec. 2, 2018, 11:28 p.m. | OK | Java 8 | TESTS | 96 | 421 | 68608000 | 2200 | |
37080533 | eatmore | E | April 7, 2018, 7:56 p.m. | OK | Java 8 | TESTS | 96 | 452 | 68608000 | 2200 | |
46527183 | kessido | E | Dec. 2, 2018, 11:27 p.m. | OK | Java 8 | TESTS | 96 | 467 | 81408000 | 2200 | |
37239532 | dalt | E | April 12, 2018, 5:12 a.m. | OK | Java 8 | TESTS | 96 | 546 | 126259200 | 2200 | |
37082536 | mathmaniac | E | April 7, 2018, 9:11 p.m. | OK | Java 8 | TESTS | 96 | 560 | 106086400 | 2200 | |
37089470 | tri | E | April 8, 2018, 6:46 a.m. | OK | Java 8 | TESTS | 96 | 576 | 173363200 | 2200 | |
38083916 | PrakharJain | E | May 10, 2018, 3:18 a.m. | OK | Java 8 | TESTS | 96 | 592 | 98713600 | 2200 | |
37068008 | ilyakor | E | April 7, 2018, 5:05 p.m. | OK | Java 8 | TESTS | 96 | 670 | 82022400 | 2200 | |
37077383 | chokudai | E | April 7, 2018, 6:20 p.m. | OK | Mono C# | TESTS | 96 | 795 | 55705600 | 2200 | |
48910501 | vjudge2 | E | Jan. 25, 2019, 1:45 a.m. | OK | MS C++ | TESTS | 96 | 234 | 20787200 | 2200 | |
37081310 | Taube | E | April 7, 2018, 8:15 p.m. | OK | MS C++ | TESTS | 96 | 264 | 33177600 | 2200 | |
37252724 | _noname absi2011 luoyuchu | E | April 12, 2018, 2:07 p.m. | OK | MS C++ | TESTS | 96 | 265 | 18944000 | 2200 | |
37636207 | pseudo | E | April 26, 2018, 12:46 p.m. | OK | MS C++ | TESTS | 96 | 280 | 53964800 | 2200 | |
47805207 | LoneFox | E | Jan. 1, 2019, 6:27 a.m. | OK | MS C++ | TESTS | 96 | 327 | 16896000 | 2200 | |
37092896 | Deamon | E | April 8, 2018, 9:37 a.m. | OK | MS C++ | TESTS | 96 | 655 | 33177600 | 2200 | |
60287509 | pajenegod | E | Sept. 9, 2019, 4:07 a.m. | OK | PyPy 2 | TESTS | 96 | 639 | 51507200 | 2200 |
Back to search problems