AtCoder Regular Contest 015

Submission #1087153

Source codeソースコード

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

ll gcd(ll a, ll b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}

struct Node {
  double ratio;
  Node() {};
  Node(double r) : ratio(r) {
  };
};

int n, unit_num;
vv<vi> g;
vector<Node> nodes;
deque<bool> reached;

void bfs(int s) {
  nodes.assign(unit_num, Node(1.0));
  reached.assign(unit_num, false);

  deque<int> st;
  st.push_back(s);
  reached[s] = true;
  while (!st.empty()) {
    int u = st.front();
    st.pop_front();
    for (auto edge : g[u]) {
      int v = edge[1];
      if (reached[v]) {
        continue;
      }
      nodes[v] = nodes[u];
      if (edge[0] > 0) {
        nodes[v].ratio *= edge[0];
      } else {
        nodes[v].ratio /= (-edge[0]);
      }
      st.push_back(v);
      reached[v] = true;
    }
  }
}

int main() {
  cin >> n;
  g.resize(n * 2);
  set<string> units;
  map<string, int> unit_id;
  rep (i, n) {
    vector<string> s(2);
    int m;
    cin >> s[0] >> m >> s[1];
    rep (j, 2) {
      if (units.find(s[j]) == end(units)) {
        unit_id[s[j]] = (int)units.size();
        units.insert(s[j]);
      }
    }
    g[unit_id[s[0]]].push_back((vi){m, unit_id[s[1]]});
    g[unit_id[s[1]]].push_back((vi){-m, unit_id[s[0]]});
  }
  unit_num = (int)units.size();
  g.resize(unit_num);
  vector<string> v_units(unit_num);
  for (auto elm : unit_id) {
    v_units[elm.second] = elm.first;
  }

  bfs(0);
  int biggest, smallest;
  biggest = smallest = 0;
  FOR (i, 1, unit_num) {
    if (nodes[i].ratio < nodes[biggest].ratio) {
      biggest = i;
    }
    if (nodes[i].ratio > nodes[smallest].ratio) {
      smallest = i;
    }
  }
  double ans = nodes[smallest].ratio / nodes[biggest].ratio;
  cout << "1" << v_units[biggest] << "=" << (int)(ans + 1e-5) << v_units[smallest] << "\n";

  return 0;
}

Submission

Task問題 C - 変わった単位
User nameユーザ名 mu
Created time投稿日時
Language言語 C++11 (GCC 4.8.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2750 Byte
File nameファイル名
Exec time実行時間 21 ms
Memory usageメモリ使用量 1052 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample_01.txt AC 20 ms 1048 KB
00_sample_02.txt AC 19 ms 928 KB
00_sample_03.txt AC 17 ms 1048 KB
chokudai_solo_01.txt AC 17 ms 1052 KB
chokudai_solo_02.txt AC 20 ms 1048 KB
chokudai_solo_03.txt AC 19 ms 924 KB
chokudai_vs_cucumber_01.txt AC 20 ms 1052 KB
chokudai_vs_cucumber_02.txt AC 20 ms 1048 KB
chokudai_vs_cucumber_03.txt AC 20 ms 1052 KB
chokudai_vs_cucumber_04.txt AC 20 ms 1048 KB
chokudai_vs_cucumber_05.txt AC 20 ms 1052 KB
chokudai_vs_kensho_01.txt AC 18 ms 1052 KB
chokudai_vs_kensho_02.txt AC 19 ms 1052 KB
chokudai_vs_kensho_03.txt AC 20 ms 1052 KB
chokudai_vs_kensho_04.txt AC 20 ms 1048 KB
chokudai_vs_kensho_05.txt AC 20 ms 928 KB
chokudai_vs_kensho_06.txt AC 20 ms 1052 KB
chokudai_vs_kensho_07.txt AC 18 ms 1052 KB
chokudai_vs_kensho_08.txt AC 19 ms 1052 KB
chokudai_vs_kensho_09.txt AC 20 ms 924 KB
chokudai_vs_laycurse_01.txt AC 20 ms 1048 KB
chokudai_vs_laycurse_02.txt AC 20 ms 1052 KB
chokudai_vs_laycurse_03.txt AC 20 ms 1048 KB
chokudai_vs_sanagipp_01.txt AC 20 ms 1052 KB
chokudai_vs_sanagipp_02.txt AC 18 ms 1052 KB
chokudai_vs_sanagipp_03.txt AC 18 ms 920 KB
chokudai_vs_sanagipp_04.txt AC 20 ms 1044 KB
chokudai_vs_takahashikun_01.txt AC 20 ms 924 KB
chokudai_vs_takahashikun_02.txt AC 20 ms 924 KB
chokudai_vs_takahashikun_03.txt AC 18 ms 1052 KB
chokudai_vs_takahashikun_04.txt AC 20 ms 1052 KB
chokudai_vs_uwitenpen_01.txt AC 21 ms 988 KB
chokudai_vs_uwitenpen_02.txt AC 20 ms 924 KB
chokudai_vs_uwitenpen_03.txt AC 19 ms 1052 KB