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 |
|---|---|---|---|---|---|---|
| 223 | Codeforces Round 138 (Div. 1) | FINISHED | False | 7200 | 428596223 | Sept. 16, 2012, 3:30 p.m. |
Solved |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
|---|---|---|---|---|---|---|
| ( 208 ) | E | Planar Graph | PROGRAMMING | flows geometry graphs | 3000 |
A graph is called planar , if it can be drawn in such a way that its edges intersect only at their vertexes. An articulation point is such a vertex of an undirected graph, that when removed increases the number of connected components of the graph. A bridge is such an edge of an undirected graph, that when removed increases the number of connected components of the graph. You've got a connected undirected planar graph consisting of n vertexes, numbered from 1 to n , drawn on the plane. The graph has no bridges, articulation points, loops and multiple edges. You are also given q queries. Each query is a cycle in the graph. The query response is the number of graph vertexes, which (if you draw a graph and the cycle on the plane) are located either inside the cycle, or on it. Write a program that, given the graph and the queries, will answer each query. The first line contains two space-separated integers n and m ( 3 ≤ n , m ≤ 10 5 ) — the number of vertexes and edges of the graph. Next m lines contain the edges of the graph: the i -th line contains two space-separated integers u i and v i ( 1 ≤ u i , v i ≤ n ) — the numbers of vertexes, connecting the i -th edge. The next n lines contain the positions of the planar graph vertexes on the plane: the i -th line contains a pair of space-separated integers x i and y i ( | x i |, | y i | ≤ 10 9 ) — the coordinates of the i -th vertex of the graph on the plane. The next line contains integer q ( 1 ≤ q ≤ 10 5 ) — the number of queries. Then follow q lines that describe the queries: the i -th line contains the sequence of space-separated integers k i , a 1 , a 2 , ..., a k i ( 1 ≤ a j ≤ n ; k i > 2 ), where k i is the cycle length in the i -th query, a j are numbers of the vertexes that form a cycle. The numbers of vertexes in the cycle are given in the clockwise or counterclockwise order. The given cycles are simple, that is they cannot go through a graph vertex more than once. The total length of all cycles in all |
| Tutorial |
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 5376290 | PSDEV | E | Dec. 7, 2013, 1:44 p.m. | OK | GNU C++ | TESTS | 53 | 186 | 12902400 | 3000 | |
| 27841871 | Scut82 | E | June 17, 2017, 8:53 a.m. | OK | GNU C++ | TESTS | 53 | 187 | 14848000 | 3000 | |
| 2787762 | ghafi007 | E | Dec. 17, 2012, 3:01 p.m. | OK | GNU C++ | TESTS | 53 | 202 | 12902400 | 3000 | |
| 40990756 | ReaLNero1 | E | July 31, 2018, 12:10 a.m. | OK | GNU C++ | TESTS | 53 | 202 | 14848000 | 3000 | |
| 15141856 | HappyNewYearMike | E | Dec. 31, 2015, 9:54 p.m. | OK | GNU C++ | TESTS | 53 | 202 | 15667200 | 3000 | |
| 35848613 | ______u______ | E | March 2, 2018, 5:01 p.m. | OK | GNU C++ | TESTS | 53 | 202 | 21606400 | 3000 | |
| 35848508 | ______n______ | E | March 2, 2018, 5:01 p.m. | OK | GNU C++ | TESTS | 53 | 202 | 21606400 | 3000 | |
| 35848241 | _____i_____ | E | March 2, 2018, 4:56 p.m. | OK | GNU C++ | TESTS | 53 | 202 | 21606400 | 3000 | |
| 35847894 | _____k_____ | E | March 2, 2018, 4:51 p.m. | OK | GNU C++ | TESTS | 53 | 202 | 21606400 | 3000 | |
| 35841352 | ______h______ | E | March 2, 2018, 2:32 p.m. | OK | GNU C++ | TESTS | 53 | 202 | 21606400 | 3000 | |
| 6519082 | Zuza | E | May 1, 2014, 9:05 p.m. | OK | GNU C++0x | TESTS | 53 | 436 | 21811200 | 3000 | |
| 6541204 | stjepan | E | May 3, 2014, 6:44 p.m. | OK | GNU C++0x | TESTS | 53 | 498 | 26828800 | 3000 | |
| 6541668 | ikatanic | E | May 3, 2014, 9:47 p.m. | OK | GNU C++0x | TESTS | 53 | 592 | 26112000 | 3000 | |
| 5872625 | ssmike | E | Feb. 3, 2014, 9:08 a.m. | OK | GNU C++0x | TESTS | 53 | 778 | 30003200 | 3000 | |
| 60733208 | sorry_im_smurfing | E | Sept. 17, 2019, 4:29 p.m. | OK | GNU C++11 | TESTS | 53 | 202 | 19456000 | 3000 | |
| 57822026 | py_ultron | E | July 27, 2019, 12:13 a.m. | OK | GNU C++11 | TESTS | 53 | 202 | 19558400 | 3000 | |
| 15917958 | fsps60312 | E | Feb. 9, 2016, 4:30 p.m. | OK | GNU C++11 | TESTS | 53 | 202 | 23040000 | 3000 | |
| 17753349 | Shik | E | May 6, 2016, 4:02 a.m. | OK | GNU C++11 | TESTS | 53 | 218 | 16896000 | 3000 | |
| 57899372 | lopare | E | July 28, 2019, 3 p.m. | OK | GNU C++11 | TESTS | 53 | 233 | 19558400 | 3000 | |
| 17271600 | I_love_chickpea | E | April 10, 2016, 9:24 p.m. | OK | GNU C++11 | TESTS | 53 | 327 | 28057600 | 3000 | |
| 13887936 | BrianKuo | E | Oct. 27, 2015, 9:39 a.m. | OK | GNU C++11 | TESTS | 53 | 327 | 30208000 | 3000 | |
| 13887942 | ntu_vjudge_2 | E | Oct. 27, 2015, 9:40 a.m. | OK | GNU C++11 | TESTS | 53 | 343 | 30208000 | 3000 | |
| 13864635 | ntu_vjudge_1 | E | Oct. 26, 2015, 12:43 a.m. | OK | GNU C++11 | TESTS | 53 | 358 | 21606400 | 3000 | |
| 12075905 | M.Mahdi | E | July 15, 2015, 9:41 p.m. | OK | GNU C++11 | TESTS | 53 | 405 | 36147200 | 3000 | |
| 56033072 | Scut82 | E | June 25, 2019, 10:40 a.m. | OK | GNU C++14 | TESTS | 53 | 155 | 11878400 | 3000 | |
| 32614847 | cyz666 | E | Nov. 24, 2017, 8:44 a.m. | OK | GNU C++14 | TESTS | 53 | 187 | 12185600 | 3000 | |
| 40637361 | teapotd | E | July 22, 2018, 1:52 p.m. | OK | GNU C++14 | TESTS | 53 | 233 | 15257600 | 3000 | |
| 49299365 | black_horse2014 | E | Feb. 1, 2019, 1:45 a.m. | OK | GNU C++14 | TESTS | 53 | 358 | 28467200 | 3000 | |
| 67271770 | ElangBondol | E | Dec. 20, 2019, 8:36 a.m. | OK | GNU C++14 | TESTS | 53 | 389 | 19660800 | 3000 | |
| 23667510 | Ali.Pi | E | Jan. 9, 2017, 5:01 p.m. | OK | GNU C++14 | TESTS | 53 | 405 | 38912000 | 3000 | |
| 49309257 | zhaominyiz | E | Feb. 1, 2019, 7:05 a.m. | OK | GNU C++14 | TESTS | 53 | 545 | 33587200 | 3000 | |
| 60458805 | Benq | E | Sept. 12, 2019, 7:22 p.m. | OK | GNU C++17 | TESTS | 53 | 249 | 37580800 | 3000 |
Back to search problems