Submission #106002


Source Code Expand

Copy
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <cmath>
#include <algorithm>

#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>

using namespace std;

typedef long long ll;

#define M (401)

int n;
vector<string> large;
vector<int> m;
vector<string> small;
map<string, int> s2i;
map<int, string> i2s;
double graph[M][M];
set<string> names;
vector<string> units;
int node;

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  cin >> n;
  for(int i = 0; i < n; i++){
    string s, l;
    int a;
    cin >> l >> a >> s;
    large.push_back(l); m.push_back(a); small.push_back(s);
    names.insert(l); names.insert(s);
  }
  for(set<string>::iterator it = names.begin(); it != names.end(); it++)
    units.push_back(*it);
  node = units.size();
  for(int i = 0; i < node; i++){
    s2i[units[i]] = i;
    i2s[i] = units[i];
  }
  memset(graph, 0, sizeof(graph));
  for(int i = 0; i < n; i++){
    int li = s2i[large[i]];
    int si = s2i[small[i]];
    graph[li][si] = m[i];
    graph[si][li] = 1.0/m[i];
  }
  double ans = 0;
  int start = -1, end = -1;
  for(int i = 0; i < node; i++){
    double mx = 1;
    int where = -1;
    double memo[M];
    for(int j = 0; j < node; j++)memo[j] = 0;
    priority_queue< pair<double, int> > q;
    q.push(make_pair(1, i));
    memo[i] = 1;
    while(!q.empty()){
      pair<double, int> p = q.top(); q.pop();
      int w = p.second;
      double d = p.first;
      if(memo[w] > d)
        continue;
      if(mx < d){
        mx = d;
        where = w;
      }
      for(int j = 0; j < node; j++)
        if(graph[w][j]){
          if(memo[j] < d * graph[w][j]){
            memo[j] = d * graph[w][j];
            q.push(make_pair(memo[j], j));
          }
        }
    }
    if(mx > ans){
      ans = mx;
      start = i; end = where;
    }
  }
  cout << "1" << i2s[start] << "=" << ans << i2s[end] << endl;

  return 0;
}

Submission Info

Submission Time
Task C - 変わった単位
User chronotable
Language C++ (G++ 4.6.4)
Score 0
Code Size 2061 Byte
Status
Exec Time 2042 ms
Memory 133292 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 2084 KB
00_sample_02.txt 24 ms 2080 KB
00_sample_03.txt 26 ms 1956 KB
chokudai_solo_01.txt 24 ms 1948 KB
chokudai_solo_02.txt 25 ms 1960 KB
chokudai_solo_03.txt 24 ms 2084 KB
chokudai_vs_cucumber_01.txt 2032 ms 6388 KB
chokudai_vs_cucumber_02.txt 2031 ms 18576 KB
chokudai_vs_cucumber_03.txt 2034 ms 67724 KB
chokudai_vs_cucumber_04.txt 2031 ms 4252 KB
chokudai_vs_cucumber_05.txt 2032 ms 34960 KB
chokudai_vs_kensho_01.txt 2030 ms 2176 KB
chokudai_vs_kensho_02.txt 1552 ms 2080 KB
chokudai_vs_kensho_03.txt 2031 ms 2208 KB
chokudai_vs_kensho_04.txt 2031 ms 6292 KB
chokudai_vs_kensho_05.txt 2032 ms 18528 KB
chokudai_vs_kensho_06.txt 2035 ms 67756 KB
chokudai_vs_kensho_07.txt 2030 ms 2212 KB
chokudai_vs_kensho_08.txt 2036 ms 10392 KB
chokudai_vs_kensho_09.txt 36 ms 2208 KB
chokudai_vs_laycurse_01.txt 2030 ms 2332 KB
chokudai_vs_laycurse_02.txt 2030 ms 2344 KB
chokudai_vs_laycurse_03.txt 2029 ms 2332 KB
chokudai_vs_sanagipp_01.txt 2030 ms 2212 KB
chokudai_vs_sanagipp_02.txt 2034 ms 2164 KB
chokudai_vs_sanagipp_03.txt 2042 ms 133292 KB
chokudai_vs_sanagipp_04.txt 2039 ms 133248 KB
chokudai_vs_takahashikun_01.txt 33 ms 2072 KB
chokudai_vs_takahashikun_02.txt 2031 ms 4252 KB
chokudai_vs_takahashikun_03.txt 2031 ms 2508 KB
chokudai_vs_takahashikun_04.txt 2030 ms 2352 KB
chokudai_vs_uwitenpen_01.txt 2033 ms 34956 KB
chokudai_vs_uwitenpen_02.txt 2034 ms 67712 KB
chokudai_vs_uwitenpen_03.txt 2034 ms 67804 KB