Submission #105710


Source Code Expand

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

using namespace std;

map<string, vector<pair<string, int> > > maps;
set<string> strs;
map<string, pair<string, int> > memo;
map<string, bool> memo2;

pair<string, int> saiki(string str) {
	if (memo2[str]) {
		return memo[str];
	}
	int 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, int> 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;
		cout << str << " " << maps[str][number].second << " " << memo[str].first << endl;
		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();
	int max = 0;
	string maxStr;
	string minStr;
	for (set<string>::iterator it = strs.begin(); it != strs.end(); it++) {
		pair<string, int> 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 1652 Byte
Status
Exec Time 365 ms
Memory 16808 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 24 ms 764 KB
00_sample_02.txt 21 ms 804 KB
00_sample_03.txt 22 ms 936 KB
chokudai_solo_01.txt 21 ms 808 KB
chokudai_solo_02.txt 289 ms 16676 KB
chokudai_solo_03.txt 295 ms 16672 KB
chokudai_vs_cucumber_01.txt 365 ms 16804 KB
chokudai_vs_cucumber_02.txt 305 ms 16804 KB
chokudai_vs_cucumber_03.txt 325 ms 16808 KB
chokudai_vs_cucumber_04.txt 323 ms 16800 KB
chokudai_vs_cucumber_05.txt 310 ms 16796 KB
chokudai_vs_kensho_01.txt 23 ms 920 KB
chokudai_vs_kensho_02.txt 24 ms 740 KB
chokudai_vs_kensho_03.txt 24 ms 804 KB
chokudai_vs_kensho_04.txt 23 ms 928 KB
chokudai_vs_kensho_05.txt 312 ms 16800 KB
chokudai_vs_kensho_06.txt 345 ms 16808 KB
chokudai_vs_kensho_07.txt 333 ms 16756 KB
chokudai_vs_kensho_08.txt 304 ms 16808 KB
chokudai_vs_kensho_09.txt 308 ms 16736 KB
chokudai_vs_laycurse_01.txt 24 ms 804 KB
chokudai_vs_laycurse_02.txt 23 ms 808 KB
chokudai_vs_laycurse_03.txt 23 ms 932 KB
chokudai_vs_sanagipp_01.txt 22 ms 792 KB
chokudai_vs_sanagipp_02.txt 22 ms 932 KB
chokudai_vs_sanagipp_03.txt 23 ms 808 KB
chokudai_vs_sanagipp_04.txt 23 ms 932 KB
chokudai_vs_takahashikun_01.txt 22 ms 800 KB
chokudai_vs_takahashikun_02.txt 21 ms 804 KB
chokudai_vs_takahashikun_03.txt 23 ms 800 KB
chokudai_vs_takahashikun_04.txt 22 ms 804 KB
chokudai_vs_uwitenpen_01.txt 24 ms 812 KB
chokudai_vs_uwitenpen_02.txt 25 ms 776 KB
chokudai_vs_uwitenpen_03.txt 22 ms 800 KB