Codeforces Round 796 (Div. 1)

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
1687 Codeforces Round 796 (Div. 1) FINISHED False 7200 77556299 June 3, 2022, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 3675 ) B Railway System PROGRAMMING constructive algorithms ds graphs greedy interactive sortings

B'This is an interactive problem. Under the direct supervision of Kanako and the Moriya Shrine, the railway system of Gensokyo is finally finished. GSKR (Gensokyo Railways) consists of n stations with m bidirectional tracks connecting them. The i -th track has length l_i ( 1 <= l_i <= 10^6 ). Due to budget limits, the railway system may not be connected, though there may be more than one track between two stations. The value of a railway system is defined as the total length of its all tracks. The maximum (or minimum) capacity of a railway system is defined as the maximum (or minimum) value among all of the currently functional system 's full spanning forest. In brief, full spanning forest of a graph is a spanning forest with the same connectivity as the given graph. Kanako has a simulator only able to process no more than 2m queries. The input of the simulator is a string s of length m , consisting of characters 0 and/or 1. The simulator will assume the i -th track functional if s_i= 1. The device will then tell Kanako the maximum capacity of the system in the simulated state. Kanako wants to know the the minimum capacity of the system with all tracks functional with the help of the simulator. The structure of the railway system is fixed in advance. In other words, the interactor is not adaptive. The first and only line of input contains two integers n,m ( 2 <= q n <= q 200 , 1 <= m <= 500 ) -- the number of stations and tracks. Begin the interaction by reading n,m . To make a query, print "? s " (without quotes, s is a string of length m , consisting of characters 0 and/or 1). Then you should read our response from standard input -- the maximum capacity of the system in the simulated state. If your program has made an invalid query or has run out of tries, the interactor will terminate immediately and your program will get a verdict Wrong answer. To give the final'...

Tutorials

Editorial of Codeforces Round 796

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
159379461 mban259 B June 3, 2022, 3:12 p.m. OK C# 10 TESTS 48 155 2560000
159361011 hos.lyric B June 3, 2022, 2:48 p.m. OK D TESTS 48 61 4198400
159375768 Gassa B June 3, 2022, 3:06 p.m. OK D TESTS 48 124 0

remove filters

Back to search problems