Submission #105483


Source Code Expand

Copy
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <string>

using namespace std;

map<string, vector<pair<string, double> > > maps;
set<string> strs;
map<string, double> memo;


pair<string, double> saiki(string str) {
	if (memo[str]) {
		return make_pair(str, memo[str]);
	}
	double maxNum = 0;
	string retStr;
	int number = 0;
	for (int i = 0; i < maps[str].size(); i++) {
		string smallStr = maps[str][i].first;
		if (strs.find(smallStr) != strs.end()) {
			pair<string, double> ret = saiki(smallStr);
			if (maxNum < ret.second) {
				maxNum = ret.second;
				retStr = ret.first;
				number = i;
			}
		}
	}
	if (maxNum == 0) {
		memo[str] = maps[str][0].second;
		return maps[str][0];
	} else {
		memo[str] = maps[str][0].second;
		return make_pair(retStr, maps[str][number].second*maxNum);
	}
}



int main(void) {

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int m;
		string large, small;
		cin >> large >> m >> small;
		maps[large].push_back(make_pair(small, m));
		strs.insert(large);
	}

	set<string>::iterator maxIt = strs.begin();
	double max = 0;
	string maxStr;
	string minStr;
	for (set<string>::iterator it = strs.begin(); it != strs.end(); it++) {
		pair<string, double> ret = saiki((*it));
		if (max < ret.second) {
			max = ret.second;
			maxStr = (*it);
			minStr = ret.first;
		}
	}

	cout << "1" << maxStr << "=" << max << minStr;

	return 0;
}

Submission Info

Submission Time
Task C - 変わった単位
User Sei
Language C++ (GCC 4.4.7)
Score 0
Code Size 1475 Byte
Status
Exec Time 412 ms
Memory 16856 KB

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 100 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, chokudai_solo_01.txt, chokudai_solo_02.txt, chokudai_solo_03.txt, chokudai_vs_cucumber_01.txt, chokudai_vs_cucumber_02.txt, chokudai_vs_cucumber_03.txt, chokudai_vs_cucumber_04.txt, chokudai_vs_cucumber_05.txt, chokudai_vs_kensho_01.txt, chokudai_vs_kensho_02.txt, chokudai_vs_kensho_03.txt, chokudai_vs_kensho_04.txt, chokudai_vs_kensho_05.txt, chokudai_vs_kensho_06.txt, chokudai_vs_kensho_07.txt, chokudai_vs_kensho_08.txt, chokudai_vs_kensho_09.txt, chokudai_vs_laycurse_01.txt, chokudai_vs_laycurse_02.txt, chokudai_vs_laycurse_03.txt, chokudai_vs_sanagipp_01.txt, chokudai_vs_sanagipp_02.txt, chokudai_vs_sanagipp_03.txt, chokudai_vs_sanagipp_04.txt, chokudai_vs_takahashikun_01.txt, chokudai_vs_takahashikun_02.txt, chokudai_vs_takahashikun_03.txt, chokudai_vs_takahashikun_04.txt, chokudai_vs_uwitenpen_01.txt, chokudai_vs_uwitenpen_02.txt, chokudai_vs_uwitenpen_03.txt
Case Name Status Exec Time Memory
00_sample_01.txt 21 ms 800 KB
00_sample_02.txt 20 ms 792 KB
00_sample_03.txt 21 ms 800 KB
chokudai_solo_01.txt 21 ms 800 KB
chokudai_solo_02.txt 273 ms 16800 KB
chokudai_solo_03.txt 270 ms 16684 KB
chokudai_vs_cucumber_01.txt 412 ms 16808 KB
chokudai_vs_cucumber_02.txt 325 ms 16812 KB
chokudai_vs_cucumber_03.txt 300 ms 16808 KB
chokudai_vs_cucumber_04.txt 322 ms 16816 KB
chokudai_vs_cucumber_05.txt 315 ms 16804 KB
chokudai_vs_kensho_01.txt 23 ms 924 KB
chokudai_vs_kensho_02.txt 23 ms 920 KB
chokudai_vs_kensho_03.txt 24 ms 808 KB
chokudai_vs_kensho_04.txt 22 ms 928 KB
chokudai_vs_kensho_05.txt 309 ms 16820 KB
chokudai_vs_kensho_06.txt 366 ms 16812 KB
chokudai_vs_kensho_07.txt 395 ms 16856 KB
chokudai_vs_kensho_08.txt 308 ms 16812 KB
chokudai_vs_kensho_09.txt 303 ms 16680 KB
chokudai_vs_laycurse_01.txt 25 ms 800 KB
chokudai_vs_laycurse_02.txt 25 ms 796 KB
chokudai_vs_laycurse_03.txt 20 ms 924 KB
chokudai_vs_sanagipp_01.txt 22 ms 812 KB
chokudai_vs_sanagipp_02.txt 22 ms 924 KB
chokudai_vs_sanagipp_03.txt 23 ms 808 KB
chokudai_vs_sanagipp_04.txt 23 ms 928 KB
chokudai_vs_takahashikun_01.txt 21 ms 900 KB
chokudai_vs_takahashikun_02.txt 23 ms 812 KB
chokudai_vs_takahashikun_03.txt 24 ms 820 KB
chokudai_vs_takahashikun_04.txt 22 ms 924 KB
chokudai_vs_uwitenpen_01.txt 22 ms 928 KB
chokudai_vs_uwitenpen_02.txt 24 ms 920 KB
chokudai_vs_uwitenpen_03.txt 22 ms 928 KB