Submission #104990


Source Code Expand

Copy
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <complex>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <functional>
#include <iterator>

using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define foreach(i,c) for(auto i=(c).begin();i!=(c).end();++i)
#define all(c) begin(c),end(c)
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INFTY=1.05e9;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

int main()
{
	for(int n;cin>>n && n;){
		map<string,int> f;
		vector<vector<pii>> g;
		rep(i,n){
			string s,t; int x; cin>>s>>x>>t;
			if(!f.count(s)){
				g.resize(g.size()+1);
				f.insert(mp(s,f.size()));
			}
			if(!f.count(t)){
				g.resize(g.size()+1);
				f.insert(mp(t,f.size()));
			}
			g[f[t]].emplace_back(f[s],x);
		}
		
		int m=g.size();
		vvi dp(m,vi(m,INFTY));
		rep(u,m) rep(i,g[u].size()){
			int v=g[u][i].first,w=g[u][i].second;
			dp[u][v]=w;
		}
		rep(k,m) rep(i,m) rep(j,m)
			if(dp[i][k]<INFTY && dp[k][j]<INFTY)
				dp[i][j]=min(dp[i][j],dp[i][k]*dp[k][j]);
		
		int u=-1,v=-1,res=0;
		rep(i,m) rep(j,m) if(dp[i][j]<INFTY && dp[i][j]>res)
			u=i,v=j,res=dp[i][j];
		
		cout<<1;
		for(auto kv:f) if(kv.second==v) cout<<kv.first<<"=";
		cout<<res;
		for(auto kv:f) if(kv.second==u) cout<<kv.first<<endl;
	}
}

Submission Info

Submission Time
Task C - 変わった単位
User lyoz
Language C++11 (GCC 4.8.1)
Score 0
Code Size 2285 Byte
Status WA
Exec Time 33 ms
Memory 1064 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 24
WA × 10
Set Name Test Cases
All 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 AC 21 ms 804 KB
00_sample_02.txt AC 20 ms 800 KB
00_sample_03.txt AC 21 ms 788 KB
chokudai_solo_01.txt AC 20 ms 680 KB
chokudai_solo_02.txt AC 21 ms 748 KB
chokudai_solo_03.txt AC 21 ms 936 KB
chokudai_vs_cucumber_01.txt AC 29 ms 1060 KB
chokudai_vs_cucumber_02.txt AC 22 ms 932 KB
chokudai_vs_cucumber_03.txt AC 22 ms 932 KB
chokudai_vs_cucumber_04.txt AC 29 ms 932 KB
chokudai_vs_cucumber_05.txt AC 22 ms 752 KB
chokudai_vs_kensho_01.txt WA 30 ms 936 KB
chokudai_vs_kensho_02.txt WA 26 ms 1056 KB
chokudai_vs_kensho_03.txt WA 31 ms 928 KB
chokudai_vs_kensho_04.txt AC 29 ms 936 KB
chokudai_vs_kensho_05.txt AC 23 ms 932 KB
chokudai_vs_kensho_06.txt AC 22 ms 932 KB
chokudai_vs_kensho_07.txt WA 30 ms 932 KB
chokudai_vs_kensho_08.txt AC 22 ms 796 KB
chokudai_vs_kensho_09.txt AC 23 ms 764 KB
chokudai_vs_laycurse_01.txt WA 32 ms 1056 KB
chokudai_vs_laycurse_02.txt WA 27 ms 868 KB
chokudai_vs_laycurse_03.txt AC 31 ms 1052 KB
chokudai_vs_sanagipp_01.txt AC 29 ms 1064 KB
chokudai_vs_sanagipp_02.txt AC 31 ms 1056 KB
chokudai_vs_sanagipp_03.txt AC 24 ms 804 KB
chokudai_vs_sanagipp_04.txt AC 31 ms 932 KB
chokudai_vs_takahashikun_01.txt WA 21 ms 808 KB
chokudai_vs_takahashikun_02.txt WA 23 ms 808 KB
chokudai_vs_takahashikun_03.txt WA 27 ms 800 KB
chokudai_vs_takahashikun_04.txt WA 30 ms 932 KB
chokudai_vs_uwitenpen_01.txt AC 33 ms 1052 KB
chokudai_vs_uwitenpen_02.txt AC 24 ms 804 KB
chokudai_vs_uwitenpen_03.txt AC 31 ms 928 KB