| Show all threads Hide all threads Show all messages Hide all messages | | Some help for C++ authors | 198808xc | 1575. Yekaterinburg Subway 2 | 29 Nov 2023 19:24 | 8 | 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. 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"}
}; | | good idea to avoid mistake | Celebrate | 1575. Yekaterinburg Subway 2 | 8 Oct 2021 04:45 | 1 | 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 | | Just Precalculate ;D | GastonFontenla | 1575. Yekaterinburg Subway 2 | 25 Aug 2015 11:01 | 1 | 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. | | Something really strange... | Vedernikoff Sergey | 1575. Yekaterinburg Subway 2 | 24 May 2013 00:04 | 5 | 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. | | It is very easy problem just Floyd algo,or BFS,or Dijsktra but WA#2,help please | Hrayr | 1575. Yekaterinburg Subway 2 | 21 Jun 2011 21:33 | 1 | 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 | | why there is a string in test#2 doesn't show up in the map ? | William Chou | 1575. Yekaterinburg Subway 2 | 20 Feb 2011 12:15 | 3 | 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. | | Some help | Samsonov Ivan (Rybinsk SAAT) | 1575. Yekaterinburg Subway 2 | 9 Jul 2010 19:57 | 8 | Some help Samsonov Ivan (Rybinsk SAAT) 15 Oct 2007 15:10 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"; | | 1905_year_square?? | strider | 1575. Yekaterinburg Subway 2 | 4 Feb 2009 03:41 | 3 | 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. | | WA2 | Lebedev_Nicolay[Ivanovo SPU] | 1575. Yekaterinburg Subway 2 | 13 Nov 2008 21:16 | 1 | WA2 Lebedev_Nicolay[Ivanovo SPU] 13 Nov 2008 21:16 what is the first character in name "I_Pyatiletki_square" | | metro 2 | svr | 1575. Yekaterinburg Subway 2 | 15 Oct 2007 22:05 | 1 | 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 | | Can I change my color at 1905_year_square ??? | Evangelion | 1575. Yekaterinburg Subway 2 | 13 Oct 2007 14:59 | 1 | |
|
|
