Divide by Zero 2018 and Codeforces Round 474 (Div. 1 + Div. 2, combined)

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.

Problems

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) ='...

Tutorials

Divide by Zero 2018 and Codeforces Round #474 (Div. 1 + Div. 2, combined) Editorial

Submissions

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

remove filters

Back to search problems