Submission #1215253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215253		vibhas	Zamjena (COCI18_zamjena)	Java	56 / 70	394 ms	88344 KiB

zamjena

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class zamjena {
    static Set<Set<String>> connected_components = new HashSet<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer first_st = new StringTokenizer(br.readLine());
        StringTokenizer second_st = new StringTokenizer(br.readLine());
        Set<String> diff_elements = new HashSet<>();
        Map<String, Set<String>> connections = new HashMap<>();
        for(int i = 0; i < n; i++){
            String a = first_st.nextToken();
            String b = second_st.nextToken();
            diff_elements.add(a);
            diff_elements.add(b);
            if(connections.containsKey(a)){
                connections.get(a).add(b);
            }else{
                Set<String> temp = new HashSet<>();
                temp.add(b);
                connections.put(a, temp);
            }
            if(connections.containsKey(b)){
                connections.get(b).add(a);
            }else{
                Set<String> temp = new HashSet<>();
                temp.add(a);
                connections.put(b, temp);
            }
        }
        boolean[] visited = new boolean[diff_elements.size()];
        Map<String, Integer> indices = new HashMap<>();
        int index = 0;
        for(String element : diff_elements){
            indices.put(element, index);
            index++;
        }
        for(String element : diff_elements){
            if(!visited[indices.get(element)]){
                Set<String> component = new HashSet<>();
                visit(element, connections, visited, indices, component);
                connected_components.add(component);
            }
        }
        boolean printed = false;
        outer:
        for(Set<String> component : connected_components){
            boolean has_num = false;
            for(String s : component){
                if(isNumeric(s)){
                    if(!has_num){
                        has_num = true;
                    }
                    else{
                        System.out.println("NE");
                        printed = true;
                        break outer;
                    }
                }
            }
        }
        if(!printed){
            System.out.println("DA");
        }
        br.close();
    }
    public static void visit(String element, Map<String, Set<String>> connections, boolean[] visited, Map<String, Integer> indices, Set<String> component){
        visited[indices.get(element)] = true;
        component.add(element);
        for(String connection :connections.get(element)){
            if(!visited[indices.get(connection)]){
                visit(connection, connections, visited, indices, component);
            }
        }
    }
    public static boolean isNumeric(String str) {
        try {
            Integer.parseInt(str);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 0 / 14