Submission #105598


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, pair<string, double> > memo;
map<string, bool> memo2;

pair<string, double> saiki(string str) {
	if (memo2[str]) {
		return 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];
		memo2[str] = true;
		return maps[str][0];

	} else {
		memo[str] = make_pair(retStr, maps[str][number].second*maxNum);
		memo2[str] = true;
		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;
	int i;
	cin >> i;
	return 0;
}

Submission Info

Submission Time
Task C - 変わった単位
User Sei
Language C++ (GCC 4.4.7)
Score 0
Code Size 1588 Byte
Status
Exec Time 370 ms
Memory 16812 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 20 ms 924 KB
00_sample_02.txt 21 ms 808 KB
00_sample_03.txt 22 ms 928 KB
chokudai_solo_01.txt 21 ms 808 KB
chokudai_solo_02.txt 283 ms 16680 KB
chokudai_solo_03.txt 295 ms 16684 KB
chokudai_vs_cucumber_01.txt 370 ms 16740 KB
chokudai_vs_cucumber_02.txt 311 ms 16812 KB
chokudai_vs_cucumber_03.txt 314 ms 16804 KB
chokudai_vs_cucumber_04.txt 311 ms 16800 KB
chokudai_vs_cucumber_05.txt 316 ms 16804 KB
chokudai_vs_kensho_01.txt 21 ms 796 KB
chokudai_vs_kensho_02.txt 22 ms 804 KB
chokudai_vs_kensho_03.txt 23 ms 804 KB
chokudai_vs_kensho_04.txt 23 ms 740 KB
chokudai_vs_kensho_05.txt 301 ms 16756 KB
chokudai_vs_kensho_06.txt 335 ms 16796 KB
chokudai_vs_kensho_07.txt 330 ms 16800 KB
chokudai_vs_kensho_08.txt 294 ms 16804 KB
chokudai_vs_kensho_09.txt 289 ms 16744 KB
chokudai_vs_laycurse_01.txt 22 ms 924 KB
chokudai_vs_laycurse_02.txt 22 ms 932 KB
chokudai_vs_laycurse_03.txt 22 ms 764 KB
chokudai_vs_sanagipp_01.txt 22 ms 800 KB
chokudai_vs_sanagipp_02.txt 22 ms 740 KB
chokudai_vs_sanagipp_03.txt 22 ms 808 KB
chokudai_vs_sanagipp_04.txt 22 ms 928 KB
chokudai_vs_takahashikun_01.txt 22 ms 928 KB
chokudai_vs_takahashikun_02.txt 23 ms 760 KB
chokudai_vs_takahashikun_03.txt 23 ms 736 KB
chokudai_vs_takahashikun_04.txt 25 ms 760 KB
chokudai_vs_uwitenpen_01.txt 23 ms 932 KB
chokudai_vs_uwitenpen_02.txt 22 ms 812 KB
chokudai_vs_uwitenpen_03.txt 22 ms 808 KB