Submission #105954


Source Code Expand

Copy
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main{
    public static void main(String[] args) throws Exception{
        new Main().run();
    }

    int n;
    String[] large;
    int[] m;
    String[] small;
    ArrayList<String> ua = new ArrayList<String>();
    HashMap<String, Integer> s2i = new HashMap<String, Integer>();
    HashMap<Integer, String> i2s = new HashMap<Integer, String>();
    double[][] graph;

    void run() throws Exception{
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        large = new String[n];
        m = new int[n];
        small = new String[n];
        HashSet<String> us = new HashSet<String>();
        for(int i = 0; i < n; i++){
            large[i] = sc.next();
            m[i] = sc.nextInt();
            small[i] = sc.next();
            us.add(large[i]); us.add(small[i]);
        }
        for(String s : us)
            ua.add(s);
        int node = ua.size();
        for(int i = 0; i < node; i++){
            s2i.put(ua.get(i), i);
            i2s.put(i, ua.get(i));
        }
        graph = new double[node][node];
        for(int i = 0; i < n; i++){
            int li = s2i.get(large[i]), si = s2i.get(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 = 0;
            int where = -1;
            double[] memo = new double[node];
            PriorityQueue<E> q = new PriorityQueue<E>();
            q.offer(new E(1, i));
            memo[i] = 1;
            while(!q.isEmpty()){
                E e = q.poll();
                if(memo[e.pos] > e.value)
                    continue;
                if(mx < e.value){
                    mx = e.value;
                    where = e.pos;
                }
                for(int j = 0; j < node; j++){
                    if(graph[e.pos][j] == 0)
                        continue;
                    double nv = e.value * graph[e.pos][j];
                    if(memo[j] < nv){
                        memo[j] = nv;
                        q.offer(new E(nv, j));
                    }
                }
            }
            if(ans < mx){
                ans = mx;
                start = i; end = where;
            }
        }
        System.out.printf("1%s=%d%s\n", i2s.get(start), (int)ans, i2s.get(end));
    }
}

class E implements Comparable<E>{
    double value;
    int pos;
    E(double a, int b){
        value = a;
        pos = b;
    }
    @Override
    public int compareTo(E e){
        return Double.compare(e.value, this.value);
    }
}

Submission Info

Submission Time
Task C - 変わった単位
User chronotable
Language Java (OpenJDK 1.7.0)
Score 0
Code Size 2785 Byte
Status
Exec Time 2195 ms
Memory 86644 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 525 ms 23864 KB
00_sample_02.txt 489 ms 23736 KB
00_sample_03.txt 503 ms 23644 KB
chokudai_solo_01.txt 493 ms 23604 KB
chokudai_solo_02.txt 494 ms 23604 KB
chokudai_solo_03.txt 526 ms 24368 KB
chokudai_vs_cucumber_01.txt 2041 ms 37508 KB
chokudai_vs_cucumber_02.txt 2040 ms 44884 KB
chokudai_vs_cucumber_03.txt 2195 ms 75048 KB
chokudai_vs_cucumber_04.txt 2039 ms 37528 KB
chokudai_vs_cucumber_05.txt 2042 ms 54712 KB
chokudai_vs_kensho_01.txt 2039 ms 33176 KB
chokudai_vs_kensho_02.txt 2038 ms 33360 KB
chokudai_vs_kensho_03.txt 2042 ms 33616 KB
chokudai_vs_kensho_04.txt 2040 ms 34952 KB
chokudai_vs_kensho_05.txt 2039 ms 48288 KB
chokudai_vs_kensho_06.txt 2042 ms 64388 KB
chokudai_vs_kensho_07.txt 2038 ms 33620 KB
chokudai_vs_kensho_08.txt 2039 ms 41052 KB
chokudai_vs_kensho_09.txt 594 ms 27992 KB
chokudai_vs_laycurse_01.txt 2039 ms 33628 KB
chokudai_vs_laycurse_02.txt 2039 ms 33748 KB
chokudai_vs_laycurse_03.txt 2039 ms 33612 KB
chokudai_vs_sanagipp_01.txt 2039 ms 31916 KB
chokudai_vs_sanagipp_02.txt 2040 ms 30676 KB
chokudai_vs_sanagipp_03.txt 2039 ms 47948 KB
chokudai_vs_sanagipp_04.txt 2046 ms 86644 KB
chokudai_vs_takahashikun_01.txt 538 ms 24708 KB
chokudai_vs_takahashikun_02.txt 2041 ms 31728 KB
chokudai_vs_takahashikun_03.txt 2038 ms 31116 KB
chokudai_vs_takahashikun_04.txt 2040 ms 30832 KB
chokudai_vs_uwitenpen_01.txt 2169 ms 64176 KB
chokudai_vs_uwitenpen_02.txt 2040 ms 39888 KB
chokudai_vs_uwitenpen_03.txt 2043 ms 54584 KB