Submission #105068


Source Code Expand

Copy
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<string.h>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<map>
#include<set>
#include<bitset>
#include<iostream>
#include<sstream>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define drep(i,n) for(int i = n-1; i >= 0; i--)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y);
#define mins(x,y) x = min(x,y);
#define pb push_back
#define snuke srand((unsigned)clock()+(unsigned)time(NULL))
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ld,int> P;
typedef vector<int> vi;

const int MX = 205, INF = 1000000000, mod = 1000000007;
const ll LINF = 1000000000000000000ll;
const double eps = 1e-9;
const int dx[4] = {-1,0,1,0}, dy[4] = {0,-1,0,1}; //<^>v

int x;
map<string,int> mp;
string nm[MX];

vector<int> to[MX], co[MX];

bool used[MX];
ld d[MX];
void dfs(int v, ld a){
	if(used[v]) return;
	used[v] = true;
	d[v] = a;
	rep(i,to[v].size()){
		int u = to[v][i];
		if(co[v][i] > 0){
			dfs(u,a*co[v][i]);
		} else {
			dfs(u,a/(-co[v][i]));
		}
	}
}

P p[MX];

int main(){
	int n, a, b, c;
	cin >> n;
	string s, t;
	rep(i,n){
		cin >> s >> c >> t;
		if(mp.find(s) == mp.end()){
			mp[s] = x;
			nm[x++] = s;
		}
		if(mp.find(t) == mp.end()){
			mp[t] = x;
			nm[x++] = t;
		}
		a = mp[s]; b = mp[t];
		to[a].pb(b); co[a].pb(c);
		to[b].pb(a); co[b].pb(-c);
	}
	
	rep(i,x) p[i] = P(0,i);
	rep(i,x){
		rep(k,x) used[k] = false;
		dfs(i,10000.0);
		rep(k,x) p[k].fi += d[k];
	}
	sort(p,p+x);
	int l = p[0].se, r = p[x-1].se;
	
	rep(k,x) used[k] = false;
	dfs(l,1.0);
	
	printf("1%s=%d%s\n",nm[l].c_str(),(int)d[r],nm[r].c_str());
	
	return 0;
}




Submission Info

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