Submission #726591

#	Time	Username	Problem	Language	Result	Execution time	Memory
726591		jnjwnwnw	Carnival (CEOI14_carnival)	Java	20 / 100	949 ms	14588 KiB

carnival

import java.util.*;
import java.io.*;
public class carnival{
    // this class isnt neeeeded, can be done difficultly using an ArrayList<Integer>[]
    private class Node{
        // 2 nodes are adjacent if asking the computer about them yeilds a 1
        private HashSet<Node> adjacent;
        private int id;
        public Node(int iid){ 
            id = iid; 
            adjacent = new HashSet<>();
            adjacent.add(this);
        }
    }

    public static void main(String[] args) throws IOException {
        new carnival();
    }

    public carnival()throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());
        Node[] nodes = new Node[n];
        for(int i = 0; i < n; i++){
            nodes[i] = new Node(i);
        }
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                if (nodes[i].adjacent.contains(nodes[j])){continue;}
                System.out.println("2 " + (i+1) + " " + (j+1));
                if (Integer.parseInt(new StringTokenizer(br.readLine()).nextToken()) == 1){
                    // are connected
                    nodes[i].adjacent.addAll(nodes[j].adjacent);
                    nodes[j].adjacent = nodes[i].adjacent;
                }
            }
        }

        HashSet<HashSet<Node>> allSets = new HashSet<>();
        for(int i = 0; i < n; i++){
            allSets.add(nodes[i].adjacent);
        }

        int[] result = new int[n];
        int r = 0;
        for(HashSet<Node> s: allSets){
            r++;
            for (Node node: s){
                result[node.id] = r;
            }
        }

        System.out.print("0 ");
        for(int i = 0; i < n-1; i++){
            System.out.print(result[i] + " ");
        } System.out.println(result[n-1]);
    }
}

• Subtask 1: 4 / 20
• Subtask 2: 4 / 20
• Subtask 3: 4 / 20
• Subtask 4: 4 / 20
• Subtask 5: 4 / 20