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"} }; Thank you! You save my time. 1024 lz good man 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"} }; 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 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. It seems that my program gives right answers to all tests, but, nevertheless, WA #2 :((( 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 But I have WA #2. All constants are correct, and I use Floyd-Worshall to find all distances. Mysterious WA... Edited by author 26.10.2008 21:06 Did you find the problem? I also use Floyd-Warshall, but WA2. 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 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 Test for you: 1 Himmash Nizhne_Isetskaya Good luck! :) ありがど ございます。 thanks for your test,I found I forgot a comma in my code. But passed compile. - - AC now. 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 But there are a lot of mistakes, for example: "Bakinskih_Kommissarov"; Try to fix and post fixed test 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 There is one mistake: Moscovskaya -> Moskovskaya Geologichecksaya -> Geologicheskaya 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"; 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... No, you are wrong. 1905_year_square is an intersection of 4 lines: yellow, red, purple and green. 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. what is the first character in name "I_Pyatiletki_square" 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 |
|