Submission #1087153
Source Code Expand
#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 Info
Submission Time | |
---|---|
Task | C - 変わった単位 |
User | tspcx |
Language | C++11 (GCC 4.8.1) |
Score | 100 |
Code Size | 2750 Byte |
Status | AC |
Exec Time | 21 ms |
Memory | 1052 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
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 | 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 |