| ENG RUS | Timus Online Judge |
Обсуждение задачи 1575. Екатеринбургское метро 2198808xc Some help for C++ authors [7] // Задача 1575. Екатеринбургское метро 2 17 окт 2010 14:18 const int MaxLength = 30; const int Lines = 8; const int MaxStation = 15; const int Stations[Lines] = {13, 10, 11, 12, 9, 14, 15, 13}; const char Line[Lines][MaxStation][MaxLength + 1] = { {"7_klyuchey", "Sortirovochnaya", "China_town", "Zarechny", "City", "1905_year_square", "Kuybyshevskaya", "Sibirskaya", "Siniye_kamni", "Lechebnaya", "Varshavskaya", "Kompressornaya", "Koltsovo"}, {"Zelyony_ostrov", "Tatishchevskaya", "Verh_Isetskaya", "Kommunarov_square", "1905_year_square", "Teatralnaya", "Vostochnaya", "Vtuzgorodok", "Kamennye_palatki", "University"}, {"MEGA", "Metallurgov", "Kraulya", "Central_stadium", "Moskovskaya", "1905_year_square", "Shevchenko", "Pionerskaya", "Turbinnaya", "Elmash", "Taganskaya"}, {"Akademicheskaya", "Yugo_zapadnaya", "Volgogradskaya", "Posadskaya", "Geologicheskaya", "Teatralnaya", "Gagarinskaya", "Komsomolskaya", "Shefskaya", "Ozyornaya", "Italyanskaya", "Kalinovskaya"}, {"Sovhoznaya", "Voennaya", "Aviatsionnaya", "Dvorets_sporta", "Geologicheskaya", "Kuybyshevskaya", "Vostochnaya", "Gagarinskaya", "Vilonovskaya"}, {"Keramicheskaya", "Vtorchermet", "Samolyotnaya", "Botanicheskaya", "Parkovaya", "Mayakovskaya", "Oborony_square", "Kuybyshevskaya", "Teatralnaya", "Shevchenko", "Uralskaya", "Zvezda", "I_Pyatiletki_square", "Pobedy"}, {"Himmash", "Nizhne_Isetskaya", "Uktusskie_Gory", "Shcherbakovskaya", "Botanicheskaya", "Chkalovskaya", "Bazhovskaya", "Geologicheskaya", "1905_year_square", "Dinamo", "Uralskaya", "Mashinostroiteley", "Uralmash", "Prospekt_Kosmonavtov", "Bakinskih_Komissarov"}, {"Moskovskaya", "Kommunarov_square", "City", "Uralskaya", "Pionerskaya", "Gagarinskaya", "Vtuzgorodok", "Sibirskaya", "Oborony_square", "Bazhovskaya", "Dvorets_sporta", "Posadskaya", "Moskovskaya"} }; Sasha Bar [TNU] Re: Some help for C++ authors [1] // Задача 1575. Екатеринбургское метро 2 14 апр 2011 00:40 Thanks a lot. Michael Plusnin (USU) Re: Some help for C++ authors // Задача 1575. Екатеринбургское метро 2 15 окт 2011 18:25 thx BaseWithoutFriends Re: Some help for C++ authors // Задача 1575. Екатеринбургское метро 2 4 ноя 2011 13:18 Thank you very much. IgorKoval(from Pskov) Re: Some help for C++ authors // Задача 1575. Екатеринбургское метро 2 17 фев 2012 17:33 Thank you! You save my time. Caesar11 Re: Some help for C++ authors [1] // Задача 1575. Екатеринбургское метро 2 19 ноя 2013 13:02 1024 lz good man Harkonnen Re: Some help for C++ authors // Задача 1575. Екатеринбургское метро 2 10 авг 2022 10:17 Thanks! :) Reformatted for C++ vector<vector<string>> a { {"7_klyuchey", "Sortirovochnaya", "China_town", "Zarechny", "City", "1905_year_square", "Kuybyshevskaya", "Sibirskaya", "Siniye_kamni", "Lechebnaya", "Varshavskaya", "Kompressornaya", "Koltsovo"}, {"Zelyony_ostrov", "Tatishchevskaya", "Verh_Isetskaya", "Kommunarov_square", "1905_year_square", "Teatralnaya", "Vostochnaya", "Vtuzgorodok", "Kamennye_palatki", "University"}, {"MEGA", "Metallurgov", "Kraulya", "Central_stadium", "Moskovskaya", "1905_year_square", "Shevchenko", "Pionerskaya", "Turbinnaya", "Elmash", "Taganskaya"}, {"Akademicheskaya", "Yugo_zapadnaya", "Volgogradskaya", "Posadskaya", "Geologicheskaya", "Teatralnaya", "Gagarinskaya", "Komsomolskaya", "Shefskaya", "Ozyornaya", "Italyanskaya", "Kalinovskaya"}, {"Sovhoznaya", "Voennaya", "Aviatsionnaya", "Dvorets_sporta", "Geologicheskaya", "Kuybyshevskaya", "Vostochnaya", "Gagarinskaya", "Vilonovskaya"}, {"Keramicheskaya", "Vtorchermet", "Samolyotnaya", "Botanicheskaya", "Parkovaya", "Mayakovskaya", "Oborony_square", "Kuybyshevskaya", "Teatralnaya", "Shevchenko", "Uralskaya", "Zvezda", "I_Pyatiletki_square", "Pobedy"}, {"Himmash", "Nizhne_Isetskaya", "Uktusskie_Gory", "Shcherbakovskaya", "Botanicheskaya", "Chkalovskaya", "Bazhovskaya", "Geologicheskaya", "1905_year_square", "Dinamo", "Uralskaya", "Mashinostroiteley", "Uralmash", "Prospekt_Kosmonavtov", "Bakinskih_Komissarov"}, {"Moskovskaya", "Kommunarov_square", "City", "Uralskaya", "Pionerskaya", "Gagarinskaya", "Vtuzgorodok", "Sibirskaya", "Oborony_square", "Bazhovskaya", "Dvorets_sporta", "Posadskaya", "Moskovskaya"} }; Mortus Re: Some help for C++ authors // Задача 1575. Екатеринбургское метро 2 29 ноя 2023 19:24 Thanks (МЕГАХОРОШ) Celebrate good idea to avoid mistake // Задача 1575. Екатеринбургское метро 2 8 окт 2021 04:45 I have some mistake in the staion name which I can't find it in my code. Then I search all the string my write and calculate LCS. The string has maximal LCS is what we want to find. Like that: int __(string ss){ if(f.find(ss)==f.end()){ int ans=0,pos=0; rep(ki,1,cnt){ mst(dp,0); for(int i=1;i<=ss.length();i++){ for(int j=1;j<=s[ki].length();j++){ if(ss[i-1]==s[ki][j-1])dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } if(dp[ss.length()][s[ki].length()]>ans)ans=dp[ss.length()][s[ki].length()],pos=ki; } return pos; } return f[ss]; } Then I got AC from wa2 Edited by author 08.10.2021 04:46 GastonFontenla Just Precalculate ;D // Задача 1575. Екатеринбургское метро 2 25 авг 2015 11:01 You can precalculate all the results in a char matrix (c++), occupies less than int. With the given memory contraints, you can doit like that. Vedernikoff Sergey Something really strange... [4] // Задача 1575. Екатеринбургское метро 2 4 ноя 2007 00:50 It seems that my program gives right answers to all tests, but, nevertheless, WA #2 :((( Tolstobrov Anatoliy[Ivanovo SPU] Re: Something really strange... [2] // Задача 1575. Екатеринбургское метро 2 4 ноя 2007 06:42 1)check better names 2)find all distance 1 - 2 1 - 3 .... 69 - 70 and after try find a b c L[a,b] + L[b,c] < L[a,c] P.S. if 1 and 2 correct check you constans Vedernikoff Sergey Re: Something really strange... [1] // Задача 1575. Екатеринбургское метро 2 4 ноя 2007 18:08 But I have WA #2. All constants are correct, and I use Floyd-Worshall to find all distances. Mysterious WA... inkognito Re: Something really strange... // Задача 1575. Екатеринбургское метро 2 5 окт 2008 18:29 Edited by author 26.10.2008 21:06 NotImplemented Re: Something really strange... // Задача 1575. Екатеринбургское метро 2 24 май 2013 00:04 Did you find the problem? I also use Floyd-Warshall, but WA2. Hrayr It is very easy problem just Floyd algo,or BFS,or Dijsktra but WA#2,help please // Задача 1575. Екатеринбургское метро 2 21 июн 2011 21:33 Now AC!!!!!!!!!!!!! And this for everybody. 1) check them names 2) check the graph 3) check the station indexes if everything is OK you'll get AC. Edited by author 21.06.2011 23:24 William Chou why there is a string in test#2 doesn't show up in the map ? [2] // Задача 1575. Екатеринбургское метро 2 17 фев 2011 14:47 I insert all string that show up in the map into index (std::map<string,int> index). And I use these code to debug: string s1,s2; cin >> s1 >> s2; if (index.find(s1) == index.end() || index.find(s2) == index.end()) while (true);//if the string doesn't show up in the map,I will get TLE. ... And I got TLE #2. Who can help me? Thanks. Sorry for my poor English. PS:It's guarantee that I won't insert wrong string into index. Edited by author 17.02.2011 14:50 Sandro (USU) Re: why there is a string in test#2 doesn't show up in the map ? [1] // Задача 1575. Екатеринбургское метро 2 18 фев 2011 00:49 Test for you: 1 Himmash Nizhne_Isetskaya Good luck! :) William Chou Re: why there is a string in test#2 doesn't show up in the map ? // Задача 1575. Екатеринбургское метро 2 20 фев 2011 12:15 ありがど ございます。 thanks for your test,I found I forgot a comma in my code. But passed compile. - - AC now. Samsonov Ivan (Rybinsk SAAT) Some help [7] // Задача 1575. Екатеринбургское метро 2 15 окт 2007 15:10 Piratek-(akaDK) Re: Some help [6] // Задача 1575. Екатеринбургское метро 2 15 ноя 2008 17:47 7_klyuchey Sortirovochnaya China_town Zarechny City 1905_year_square Kuybyshevskaya Sibirskaya Siniye_kamni Lechebnaya Varshavskaya Kompressornaya Koltsovo Zelyony_ostrov Tatishchevskaya Verh_Isetskaya Kommunarov_square 1905_year_square Teatralnaya Vostochnaya Vtuzgorodok Kamennye palatki University MEGA Metallurgov Kraulya Central_stadium Moscovskaya 1905_year_square Shevchenko Pionerskaya Turbinaya Elmash Taganskaya Akademicheskaya Yugo_zapadnaya Volgogradskaya Posadskaya Geologicheskaya Teatralnaya Gagarinskaya Komsomolskaya Shefskaya Ozyornaya Italyanskaya Kalinovskaya Sovhoznaya Voennaya Aviatsionnaya Dvorets_sporta Geologicheskaya Kuybyshevskaya Vostochnaya Gagarinskaya Vilonovskaya Keramicheskaya Vtorchemet Samolyotnaya Botanicheskaya Parkovaya Mayakovskaya Oborony_square Kuybyshevskaya Teatralnaya Shevchenko Uralskaya Zvezda I_Pyatiletki_square Pobedy Himmash Nizhne_Isetskaya Uktusskie_Gory Shcherbakovskaya Botanicheskaya Chkalovskaya Bazhovskaya Geologichecksaya 1905_year_square Dinamo Uralskaya Mashinostroiteley Uralmash Prospekt_Kosmonavtov Bakinskih_Kommissarov Lebedev_Nicolay[Ivanovo SPU] Re: Some help [5] // Задача 1575. Екатеринбургское метро 2 15 ноя 2008 20:26 But there are a lot of mistakes, for example: "Bakinskih_Kommissarov"; Piratek-(akaDK) Re: Some help [4] // Задача 1575. Екатеринбургское метро 2 16 ноя 2008 01:17 Try to fix and post fixed test Piratek-(akaDK) Re: Some help [3] // Задача 1575. Екатеринбургское метро 2 28 ноя 2008 11:48 7_klyuchey Sortirovochnaya China_town Zarechny City 1905_year_square Kuybyshevskaya Sibirskaya Siniye_kamni Lechebnaya Varshavskaya Kompressornaya Koltsovo Zelyony_ostrov Tatishchevskaya Verh_Isetskaya Kommunarov_square 1905_year_square Teatralnaya Vostochnaya Vtuzgorodok Kamennye_palatki University MEGA Metallurgov Kraulya Central_stadium Moscovskaya 1905_year_square Shevchenko Pionerskaya Turbinnaya Elmash Taganskaya Akademicheskaya Yugo_zapadnaya Volgogradskaya Posadskaya Geologicheskaya Teatralnaya Gagarinskaya Komsomolskaya Shefskaya Ozyornaya Italyanskaya Kalinovskaya Sovhoznaya Voennaya Aviatsionnaya Dvorets_sporta Geologicheskaya Kuybyshevskaya Vostochnaya Gagarinskaya Vilonovskaya Keramicheskaya Vtorchermet Samolyotnaya Botanicheskaya Parkovaya Mayakovskaya Oborony_square Kuybyshevskaya Teatralnaya Shevchenko Uralskaya Zvezda I_Pyatiletki_square Pobedy Himmash Nizhne_Isetskaya Uktusskie_Gory Shcherbakovskaya Botanicheskaya Chkalovskaya Bazhovskaya Geologichecksaya 1905_year_square Dinamo Uralskaya Mashinostroiteley Uralmash Prospekt_Kosmonavtov Bakinskih_Komissarov Lebedev_Nicolay[Ivanovo SPU] Re: Some help // Задача 1575. Екатеринбургское метро 2 16 дек 2008 20:32 There is one mistake: Moscovskaya -> Moskovskaya Tralfamador Re: Some help [1] // Задача 1575. Екатеринбургское метро 2 8 июл 2009 03:15 Geologichecksaya -> Geologicheskaya Moonstone Re: Some help // Задача 1575. Екатеринбургское метро 2 9 июл 2010 19:57 This is a part of my accepted program: final String _7_klyuchey = "7_klyuchey"; final String _Sortirovochnaya = "Sortirovochnaya"; final String _China_town = "China_town"; final String _Zarechny = "Zarechny"; final String _Pobedy = "Pobedy"; final String _I_Pyatiletki_square = "I_Pyatiletki_square"; final String _Zvezda = "Zvezda"; final String _Bakinskih_Komissarov = "Bakinskih_Komissarov"; final String _Prospekt_Kosmonavtov = "Prospekt_Kosmonavtov"; final String _Uralmash = "Uralmash"; final String _Mashinostroiteley = "Mashinostroiteley"; final String _Taganskaya = "Taganskaya"; final String _Elmash = "Elmash"; final String _Turbinnaya = "Turbinnaya"; final String _Vilonovskaya = "Vilonovskaya"; final String _Kalinovskaya = "Kalinovskaya"; final String _Italyanskaya = "Italyanskaya"; final String _Ozyornaya = "Ozyornaya"; final String _Shefskaya = "Shefskaya"; final String _Komsomolskaya = "Komsomolskaya"; final String _Kamennye_palatki = "Kamennye_palatki"; final String _University = "University"; final String _Siniye_kamni = "Siniye_kamni"; final String _Lechebnaya = "Lechebnaya"; final String _Varshavskaya = "Varshavskaya"; final String _Kompressornaya = "Kompressornaya"; final String _Koltsovo = "Koltsovo"; final String _Mayakovskaya = "Mayakovskaya"; final String _Parkovaya = "Parkovaya"; final String _Botanicheskaya = "Botanicheskaya"; final String _Samolyotnaya = "Samolyotnaya"; final String _Vtorchermet = "Vtorchermet"; final String _Keramicheskaya = "Keramicheskaya"; final String _Chkalovskaya = "Chkalovskaya"; final String _Shcherbakovskaya = "Shcherbakovskaya"; final String _Uktusskie_Gory = "Uktusskie_Gory"; final String _Nizhne_Isetskaya = "Nizhne_Isetskaya"; final String _Himmash = "Himmash"; final String _Aviatsionnaya = "Aviatsionnaya"; final String _Voennaya = "Voennaya"; final String _Sovhoznaya = "Sovhoznaya"; final String _Volgogradskaya = "Volgogradskaya"; final String _Yugo_zapadnaya = "Yugo_zapadnaya"; final String _Akademicheskaya = "Akademicheskaya"; final String _Central_stadium = "Central_stadium"; final String _Kraulya = "Kraulya"; final String _Metallurgov = "Metallurgov"; final String _MEGA = "MEGA"; final String _Verh_Isetskaya = "Verh_Isetskaya"; final String _Tatishchevskaya = "Tatishchevskaya"; final String _Zelyony_ostrov = "Zelyony_ostrov"; final String _City = "City"; final String _Uralskaya = "Uralskaya"; final String _Pionerskaya = "Pionerskaya"; final String _Gagarinskaya = "Gagarinskaya"; final String _Vtuzgorodok = "Vtuzgorodok"; final String _Sibirskaya = "Sibirskaya"; final String _Oborony_square = "Oborony_square"; final String _Bazhovskaya = "Bazhovskaya"; final String _Dvorets_sporta = "Dvorets_sporta"; final String _Posadskaya = "Posadskaya"; final String _Moskovskaya = "Moskovskaya"; final String _Kommunarov_square = "Kommunarov_square"; final String _Dinamo = "Dinamo"; final String _Shevchenko = "Shevchenko"; final String _1905_year_square = "1905_year_square"; final String _Teatralnaya = "Teatralnaya"; final String _Vostochnaya = "Vostochnaya"; final String _Geologicheskaya = "Geologicheskaya"; final String _Kuybyshevskaya = "Kuybyshevskaya"; strider 1905_year_square?? [2] // Задача 1575. Екатеринбургское метро 2 3 фев 2009 17:04 There is TWO 1905_year_square: 1st is yellow-red 2nd is purple-green and there is no transition between them! Am i right? Then stations (graph vertices) count to 71. And the path from "Shevchenko" to "1905_year_square" is 1 or 2 depending where we go! So, i also have WA#2 and think maybe here is my fault... Sandro (USU) Re: 1905_year_square?? [1] // Задача 1575. Екатеринбургское метро 2 4 фев 2009 00:38 No, you are wrong. 1905_year_square is an intersection of 4 lines: yellow, red, purple and green. strider Re: 1905_year_square?? // Задача 1575. Екатеринбургское метро 2 4 фев 2009 03:41 Yes, thanks. But the picture is tangling. Two-colored circles must have suggested that there is a transition between two stations if there exists a circle with sectors of the two colors. This condition is true everywhere except 1905_year_square. On the other hand, there is no circle where yellow and green branches come and outcome together (what could be another intuitive criteria). So there is no reason to consider the two disputable circles as one station but their nearness. Lebedev_Nicolay[Ivanovo SPU] WA2 // Задача 1575. Екатеринбургское метро 2 13 ноя 2008 21:16 what is the first character in name "I_Pyatiletki_square" svr metro 2 // Задача 1575. Екатеринбургское метро 2 15 окт 2007 22:05 You have fantastic metro 1 and strange metro2 as butifull piramida 2 and trivial piramida 3 To solve this problem we must implement handfully notions of all Moskow stations. It is terrible. Edited by author 31.10.2007 20:31 Evangelion Can I change my color at 1905_year_square ??? // Задача 1575. Екатеринбургское метро 2 13 окт 2007 14:59
|