Submission #105458


Source Code Expand

Copy
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <stdio.h>
#include <complex>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef vector<LL> VLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define MT(a,b,c) MP(a, MP(b, c))

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

map<string, int> msi;
map<int, string> mis;
vector<vector<pair<int, double> > > g;
vector<bool> visit;

pair<double, int> DFS(int k){
	if(visit[k])return MP(1.0, k);
	visit[k] = true;
	double mr = 1.0;
	int mk=k;
	REP(i,g[k].size()){
		pair<double, int> tmp = DFS(g[k][i].first);
		if(mr < g[k][i].second*tmp.first){
			mr = g[k][i].second*tmp.first;
			mk = tmp.second;
		}
	}
	return MP(mr, mk);
}

int main(){
	int n;
	cin>>n;
	REP(i,n){
		string s1, s2;
		int ratio,k1,k2;
		cin>>s1>>ratio>>s2;
		if(!EXIST(msi, s1)){
			msi[s1]=msi.size();
			mis[msi[s1]]=s1;
			g.PB(vector<pair<int, double> >(0));
		}
		if(!EXIST(msi, s2)){
			msi[s2]=msi.size();
			mis[msi[s2]]=s2;
			g.PB(vector<pair<int, double> >(0));
		}
		k1 = msi[s1];
		k2 = msi[s2];
		g[k2].PB(MP(k1, ratio));
		g[k1].PB(MP(k2, 1.0/ratio));
	}
	int maxk=-1;
	int mink=-1;
	int maxR=1;
	REP(i, msi.size()){
		visit = vector<bool>(msi.size(), false);
		pair<double, int> tmp=DFS(i);
		if(tmp.first > maxR){
			maxR = tmp.first;
			maxk = i;
			mink = tmp.second;
		}
	}
	printf("1%s=%d%s\n", mis[maxk].c_str(), maxR, mis[mink].c_str());
	return 0;
}

Submission Info

Submission Time
Task C - 変わった単位
User UminchuR
Language C++ (G++ 4.6.4)
Score 0
Code Size 2716 Byte
Status
Exec Time 262 ms
Memory 924 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 239 ms 796 KB
00_sample_02.txt 241 ms 784 KB
00_sample_03.txt 237 ms 800 KB
chokudai_solo_01.txt 233 ms 796 KB
chokudai_solo_02.txt 242 ms 924 KB
chokudai_solo_03.txt 238 ms 792 KB
chokudai_vs_cucumber_01.txt 242 ms 796 KB
chokudai_vs_cucumber_02.txt 254 ms 800 KB
chokudai_vs_cucumber_03.txt 254 ms 804 KB
chokudai_vs_cucumber_04.txt 233 ms 796 KB
chokudai_vs_cucumber_05.txt 235 ms 792 KB
chokudai_vs_kensho_01.txt 239 ms 792 KB
chokudai_vs_kensho_02.txt 243 ms 796 KB
chokudai_vs_kensho_03.txt 246 ms 792 KB
chokudai_vs_kensho_04.txt 238 ms 800 KB
chokudai_vs_kensho_05.txt 257 ms 800 KB
chokudai_vs_kensho_06.txt 262 ms 788 KB
chokudai_vs_kensho_07.txt 238 ms 800 KB
chokudai_vs_kensho_08.txt 254 ms 796 KB
chokudai_vs_kensho_09.txt 229 ms 796 KB
chokudai_vs_laycurse_01.txt 229 ms 796 KB
chokudai_vs_laycurse_02.txt 233 ms 792 KB
chokudai_vs_laycurse_03.txt 229 ms 796 KB
chokudai_vs_sanagipp_01.txt 251 ms 752 KB
chokudai_vs_sanagipp_02.txt 238 ms 920 KB
chokudai_vs_sanagipp_03.txt 239 ms 800 KB
chokudai_vs_sanagipp_04.txt 241 ms 796 KB
chokudai_vs_takahashikun_01.txt 246 ms 796 KB
chokudai_vs_takahashikun_02.txt 239 ms 800 KB
chokudai_vs_takahashikun_03.txt 244 ms 800 KB
chokudai_vs_takahashikun_04.txt 246 ms 800 KB
chokudai_vs_uwitenpen_01.txt 234 ms 792 KB
chokudai_vs_uwitenpen_02.txt 246 ms 916 KB
chokudai_vs_uwitenpen_03.txt 238 ms 700 KB