Submission #308112


Source Code Expand

Copy
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int,double> P;
double memo[400];
vector<P> G[400];
void solve(int idx) {
	for(int i=0;i<G[idx].size();i++) {
		P p=G[idx][i];
		if(memo[p.first]==-1) {
			memo[p.first]=memo[idx]*p.second;
			solve(p.first);
		}
	}
}
int main() {
	int N;
	cin>>N;
	map<string,int> en;
	vector<string> de;
	for(int i=0;i<N;i++) {
		string large,small;
		int m,L,S;
		cin>>large>>m>>small;
		if(en.find(large)==en.end()) {
			L=en.size();
			en[large]=L;
			de.push_back(large);
		}else {
			L=en[large];
		}
		if(en.find(small)==en.end()) {
			S=en.size();
			en[small]=S;
			de.push_back(small);
		}else {
			S=en[small];
		}
		G[L].push_back(P(S,1.0/m));
		G[S].push_back(P(L,m));
	}
	fill(memo,memo+400,-1);
	memo[0]=1;
	solve(0);
	int L=0,S=0;
	for(int i=0;i<en.size();i++) {
		if(memo[L]<memo[i]) L=i;
		if(memo[S]>memo[i]) S=i;
	}
	cout<<"1"<<de[L]<<"="<<(int)(memo[L]/memo[S])<<de[S]<<endl;
}

Submission Info

Submission Time
Task C - 変わった単位
User Div9851
Language C++ (G++ 4.6.4)
Score 0
Code Size 1080 Byte
Status
Exec Time 27 ms
Memory 932 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 23 ms 932 KB
00_sample_02.txt 24 ms 796 KB
00_sample_03.txt 27 ms 812 KB
chokudai_solo_01.txt 24 ms 796 KB
chokudai_solo_02.txt 25 ms 928 KB
chokudai_solo_03.txt 24 ms 932 KB
chokudai_vs_cucumber_01.txt 24 ms 800 KB
chokudai_vs_cucumber_02.txt 23 ms 808 KB
chokudai_vs_cucumber_03.txt 24 ms 800 KB
chokudai_vs_cucumber_04.txt 24 ms 804 KB
chokudai_vs_cucumber_05.txt 25 ms 804 KB
chokudai_vs_kensho_01.txt 25 ms 928 KB
chokudai_vs_kensho_02.txt 26 ms 800 KB
chokudai_vs_kensho_03.txt 24 ms 804 KB
chokudai_vs_kensho_04.txt 24 ms 812 KB
chokudai_vs_kensho_05.txt 25 ms 928 KB
chokudai_vs_kensho_06.txt 24 ms 932 KB
chokudai_vs_kensho_07.txt 26 ms 796 KB
chokudai_vs_kensho_08.txt 25 ms 748 KB
chokudai_vs_kensho_09.txt 25 ms 804 KB
chokudai_vs_laycurse_01.txt 25 ms 928 KB
chokudai_vs_laycurse_02.txt 23 ms 804 KB
chokudai_vs_laycurse_03.txt 24 ms 784 KB
chokudai_vs_sanagipp_01.txt 27 ms 808 KB
chokudai_vs_sanagipp_02.txt 26 ms 932 KB
chokudai_vs_sanagipp_03.txt 24 ms 928 KB
chokudai_vs_sanagipp_04.txt 25 ms 812 KB
chokudai_vs_takahashikun_01.txt 24 ms 796 KB
chokudai_vs_takahashikun_02.txt 23 ms 808 KB
chokudai_vs_takahashikun_03.txt 27 ms 796 KB
chokudai_vs_takahashikun_04.txt 24 ms 920 KB
chokudai_vs_uwitenpen_01.txt 23 ms 800 KB
chokudai_vs_uwitenpen_02.txt 23 ms 804 KB
chokudai_vs_uwitenpen_03.txt 25 ms 800 KB