Codeforces Round 630 (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
1332 Codeforces Round 630 (Div. 2) FINISHED False 9000 146161499 March 31, 2020, 1:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 1018 ) F Independent Set PROGRAMMING dfs and similar dp trees 2500

B"Eric is the teacher of graph theory class. Today, Eric teaches independent set and edge-induced subgraph. Given a graph G=(V,E) , an independent set is a subset of vertices V' subset V such that for every pair u,v in V' , (u,v) not in E (i.e. no edge in E connects two vertices from V' ). An edge-induced subgraph consists of a subset of edges E' subset E and all the vertices in the original graph that are incident on at least one edge in the subgraph. Given E' subset E , denote G[E'] the edge-induced subgraph such that E' is the edge set of the subgraph. Here is an illustration of those definitions: In order to help his students get familiar with those definitions, he leaves the following problem as an exercise: Given a tree G=(V,E) , calculate the sum of w(H) over all except null edge-induced subgraph H of G , where w(H) is the number of independent sets in H . Formally, calculate sum limits_{ emptyset not= E' subset E} w(G[E']) . Show Eric that you are smarter than his students by providing the correct answer as quickly as possible. Note that the answer might be large, you should output the answer modulo 998,244,353 . The first line contains a single integer n ( 2 <= n <= 3 cdot 10^5 ), representing the number of vertices of the graph G . Each of the following n-1 lines contains two integers u and v ( 1 <= u,v <= n , u not= v ), describing edges of the given tree. It is guaranteed that the given edges form a tree. Output one integer, representing the desired value modulo 998,244,353 . For the second example, all independent sets are listed below. "...

Tutorials

Codeforces Round #630 Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
74980174 rainboy F March 31, 2020, 3:22 p.m. OK GNU C11 TESTS 112 202 38400000 2500
75031350 liqing F April 1, 2020, 1:52 a.m. OK GNU C++11 TESTS 112 93 17305600 2500
75071616 lzoilxy F April 1, 2020, 11:11 a.m. OK GNU C++11 TESTS 112 93 51302400 2500
75491192 OIer_whx F April 4, 2020, 1:56 p.m. OK GNU C++11 TESTS 112 109 33587200 2500
75351602 froggyzhang F April 3, 2020, 2:14 p.m. OK GNU C++11 TESTS 112 109 39628800 2500
75475378 lzoilxy F April 4, 2020, 10:19 a.m. OK GNU C++11 TESTS 112 109 51302400 2500
75030412 cmwqf F April 1, 2020, 1:22 a.m. OK GNU C++11 TESTS 112 124 20377600 2500
75194641 suncongbo F April 2, 2020, 2:51 a.m. OK GNU C++11 TESTS 112 124 33587200 2500
74992732 I_AM_SOOKE_I_AKed_IOI F March 31, 2020, 3:58 p.m. OK GNU C++11 TESTS 112 124 39628800 2500
74991793 Frame_. F March 31, 2020, 3:55 p.m. OK GNU C++11 TESTS 112 124 46796800 2500
75301071 caidzh F April 3, 2020, 2:16 a.m. OK GNU C++11 TESTS 112 124 59289600 2500
76314889 CitricAcid F April 12, 2020, 10:11 a.m. OK GNU C++14 TESTS 112 218 39628800 2500
75234163 lzt_love_huan F April 2, 2020, 11:54 a.m. OK GNU C++14 TESTS 112 233 32358400 2500
75722023 Kirito F April 7, 2020, 7:39 a.m. OK GNU C++14 TESTS 112 233 32460800 2500
75722055 vjudge1 F April 7, 2020, 7:39 a.m. OK GNU C++14 TESTS 112 234 32460800 2500
74988892 Redpojoe F March 31, 2020, 3:47 p.m. OK GNU C++14 TESTS 112 249 37171200 2500
75800263 Wolf. F April 8, 2020, 4:07 a.m. OK GNU C++14 TESTS 112 280 31436800 2500
75684330 meowmeow321 F April 6, 2020, 6:07 p.m. OK GNU C++14 TESTS 112 280 36249600 2500
75273285 collapse F April 2, 2020, 5:47 p.m. OK GNU C++14 TESTS 112 280 39833600 2500
75840997 Combi F April 8, 2020, 1:55 p.m. OK GNU C++14 TESTS 112 295 31436800 2500
75532521 zxyl F April 5, 2020, 4:11 a.m. OK GNU C++14 TESTS 112 295 35020800 2500
75027289 w33z8kqrqk8zzzx33 F March 31, 2020, 11:49 p.m. OK GNU C++17 TESTS 112 202 44032000 2500
75746914 tyzc F April 7, 2020, 1:11 p.m. OK GNU C++17 TESTS 112 233 37171200 2500
76320213 interestingLSY F April 12, 2020, 11:29 a.m. OK GNU C++17 TESTS 112 233 40857600 2500
75047655 hnust_zhangpeng F April 1, 2020, 6:44 a.m. OK GNU C++17 TESTS 112 233 41984000 2500
75287247 sharpener F April 2, 2020, 8:07 p.m. OK GNU C++17 TESTS 112 249 33587200 2500
75590952 lukelmouse F April 5, 2020, 5:01 p.m. OK GNU C++17 TESTS 112 249 37273600 2500
75024323 limbo.null F March 31, 2020, 10:18 p.m. OK GNU C++17 TESTS 112 249 37683200 2500
75658199 ILLLZKQF F April 6, 2020, 1 p.m. OK GNU C++17 TESTS 112 249 60006400 2500
75660509 LowR F April 6, 2020, 1:27 p.m. OK GNU C++17 TESTS 112 280 42188800 2500
75034298 2014CAIS01 F April 1, 2020, 3:09 a.m. OK GNU C++17 TESTS 112 295 26624000 2500
75478045 ivan100sic F April 4, 2020, 10:55 a.m. OK GNU C++17 (64) TESTS 112 202 57651200 2500
75228589 WGree F April 2, 2020, 10:52 a.m. OK GNU C++17 (64) TESTS 112 264 48128000 2500
75052195 achvanov F April 1, 2020, 7:35 a.m. OK GNU C++17 (64) TESTS 112 265 44441600 2500
75013583 Ari F March 31, 2020, 7:10 p.m. OK GNU C++17 (64) TESTS 112 265 48128000 2500
75018157 ecnerwala F March 31, 2020, 8:15 p.m. OK GNU C++17 (64) TESTS 112 265 55296000 2500
75314437 wassim.omais F April 3, 2020, 6:26 a.m. OK GNU C++17 (64) TESTS 112 265 59187200 2500
75028604 860579 F April 1, 2020, 12:28 a.m. OK GNU C++17 (64) TESTS 112 280 54067200 2500
75314200 wassim.omais F April 3, 2020, 6:22 a.m. OK GNU C++17 (64) TESTS 112 280 54476800 2500
75193244 mugen1337 F April 2, 2020, 2:12 a.m. OK GNU C++17 (64) TESTS 112 280 55296000 2500
75176470 timf1089 F April 1, 2020, 7:36 p.m. OK GNU C++17 (64) TESTS 112 280 57651200 2500
75323903 poursoul F April 3, 2020, 8:42 a.m. OK Go TESTS 112 311 128204800 2500
75575434 happy15 F April 5, 2020, 1:55 p.m. OK Java 11 TESTS 112 1310 84275200 2500
75576336 happy15 F April 5, 2020, 2:05 p.m. OK Java 11 TESTS 112 1340 84275200 2500
76308997 foumani F April 12, 2020, 9:11 a.m. OK Java 11 TESTS 112 1512 151347200 2500
76308758 foumani F April 12, 2020, 9:08 a.m. OK Java 11 TESTS 112 1528 151449600 2500
75049993 lucifer1005 F April 1, 2020, 7:09 a.m. OK Java 11 TESTS 112 1716 138137600 2500
74986268 cwise F March 31, 2020, 3:39 p.m. OK Java 8 TESTS 112 717 143462400 2500
75626144 derrick20 F April 6, 2020, 5:32 a.m. OK Java 8 TESTS 112 764 178278400 2500
75613172 Tomg F April 5, 2020, 11:36 p.m. OK Java 8 TESTS 112 810 146124800 2500
75524458 YahiaSherif F April 4, 2020, 10:52 p.m. OK Java 8 TESTS 112 842 128102400 2500
75767478 csullivan203 F April 7, 2020, 4:50 p.m. OK Java 8 TESTS 112 889 128102400 2500
75524408 YahiaSherif F April 4, 2020, 10:50 p.m. OK Java 8 TESTS 112 936 128204800 2500
75184744 O_E F April 1, 2020, 9:48 p.m. OK Java 8 TESTS 112 951 134451200 2500
75092818 polyakoff F April 1, 2020, 2:37 p.m. OK Java 8 TESTS 112 951 135680000 2500
75045994 nagabhushan F April 1, 2020, 6:25 a.m. OK Java 8 TESTS 112 1513 259379200 2500
75228582 camypaper F April 2, 2020, 10:52 a.m. OK Mono C# TESTS 112 701 234905600 2500
74982232 pichulia F March 31, 2020, 3:27 p.m. OK MS C++ 2017 TESTS 112 373 40857600 2500
75518370 RomeoFantastik F April 4, 2020, 8:09 p.m. OK MS C++ 2017 TESTS 112 701 34918400 2500
74992190 pajenegod F March 31, 2020, 3:57 p.m. OK PyPy 2 TESTS 112 841 52940800 2500
75489471 _cielll_ F April 4, 2020, 1:36 p.m. OK PyPy 3 TESTS 112 1794 113868800 2500
74981863 pineriver F March 31, 2020, 3:26 p.m. OK PyPy 3 TESTS 112 1918 114176000 2500
74978977 sansen F March 31, 2020, 3:18 p.m. OK Rust TESTS 112 280 27955200 2500
75002004 cotton100pc F March 31, 2020, 5:26 p.m. OK Rust TESTS 112 343 39833600 2500

remove filters

Back to search problems