fork download
copy 
  1. import javax.swing.*;
  2. import java.util.*;
  3. import java.io.*;
  4.  
  5. import static java.lang.Math.max;
  6. import static java.lang.Math.min;
  7. import static java.lang.Math.abs;
  8.  
  9. public class Main {
  10.     public static int mod = (int) 1e9 + 7;
  11.  
  12.     static class FastReader {
  13.         BufferedReader br;
  14.         StringTokenizer st;
  15.  
  16.         public FastReader() {
  17.             br = new BufferedReader(new InputStreamReader(System.in));
  18.         }
  19.  
  20.         String next() {
  21.             while (st == null || !st.hasMoreTokens()) {
  22.                 try {
  23.                     st = new StringTokenizer(br.readLine());
  24.                 } catch (IOException e) {
  25.                     e.printStackTrace();
  26.                 }
  27.             }
  28.             return st.nextToken();
  29.         }
  30.  
  31.         int nextInt() {
  32.             return Integer.parseInt(next());
  33.         }
  34.  
  35.         long nextLong() {
  36.             return Long.parseLong(next());
  37.         }
  38.  
  39.         double nextDouble() {
  40.             return Double.parseDouble(next());
  41.         }
  42.  
  43.         String nextLine() {
  44.             String str = "";
  45.             try {
  46.                 str = br.readLine().trim();
  47.             } catch (Exception e) {
  48.                 e.printStackTrace();
  49.             }
  50.             return str;
  51.         }
  52.     }
  53.  
  54.     static class FastWriter {
  55.         private final BufferedWriter bw;
  56.  
  57.         public FastWriter() {
  58.             this.bw = new BufferedWriter(new OutputStreamWriter(System.out));
  59.         }
  60.  
  61.         public void print(Object object) throws IOException {
  62.             bw.append("" + object);
  63.         }
  64.  
  65.         public void println(Object object) throws IOException {
  66.             print(object);
  67.             bw.append("\n");
  68.         }
  69.  
  70.         public void println() throws IOException {
  71.             bw.append("\n");
  72.         }
  73.  
  74.         public void close() throws IOException {
  75.             bw.close();
  76.         }
  77.  
  78.         public void printLongArr(long[] arr) throws IOException {
  79.             for (long ele : arr) {
  80.                 print(ele + " ");
  81.             }
  82.             println();
  83.         }
  84.  
  85.         public void printIntArr(int[] arr) throws IOException {
  86.             for (int ele : arr) {
  87.                 print(ele + " ");
  88.             }
  89.             println();
  90.         }
  91.     }
  92.  
  93.     public static void bfs(int node, int[] dist, int n, BitSet[] graph) {
  94.         BitSet visited = new BitSet();
  95.         BitSet frontier = new BitSet(); // queue
  96.  
  97.         Arrays.fill(dist, -1);
  98.         dist[node] = 0;
  99.         int level = 0;
  100.         frontier.set(node);
  101.         visited.set(node);
  102.         while (!frontier.isEmpty()) {
  103.             BitSet nextLevel = new BitSet();
  104.             for (int u = frontier.nextSetBit(0); u != -1; u = frontier.nextSetBit(u + 1)) { // level order traversal
  105.                 BitSet neighbours = (BitSet) graph[u].clone();
  106.                 neighbours.andNot(visited);
  107.                 nextLevel.or(neighbours);
  108.             }
  109.             level++;
  110.             for (int v = nextLevel.nextSetBit(0); v != -1; v = nextLevel.nextSetBit(v + 1)) {
  111.                 dist[v] = level;
  112.             }
  113.             visited.or(nextLevel);
  114.             frontier = nextLevel;
  115.         }
  116.     }
  117.  
  118.     public static String bfs2(int node, BitSet[] graph) {
  119.         BitSet visited = new BitSet();
  120.         BitSet frontier = new BitSet(); // queue
  121.  
  122.         int level = 0;
  123.         frontier.set(node);
  124.         visited.set(node);
  125.         while (!frontier.isEmpty()) {
  126.             level++;
  127.             BitSet nextLevel = new BitSet();
  128.             for (int u = frontier.nextSetBit(0); u != -1; u = frontier.nextSetBit(u + 1)) { // level order traversal
  129.                 BitSet neighbours = (BitSet) graph[u].clone();
  130.                 if(neighbours.get(node)) {
  131.                     return String.valueOf(level);
  132.                 }
  133.                 neighbours.andNot(visited);
  134.                 nextLevel.or(neighbours);
  135.             }
  136.             visited.or(nextLevel);
  137.             frontier = nextLevel;
  138.         }
  139.         return "NO WAY";
  140.     }
  141.  
  142.     public static void main
  143.             (String[] args) {
  144.         try {
  145.             FastReader fin = new FastReader();
  146.             FastWriter fout = new FastWriter();
  147.  
  148.             int n = fin.nextInt();
  149.             BitSet[] graph = new BitSet[n];
  150.    //         BitSet[] rev = new BitSet[n];
  151.             for (int i = 0; i < n; i++) {
  152.                 graph[i] = new BitSet(n);
  153.    //             rev[i] = new BitSet(n);
  154.             }
  155.             for (int i = 0; i < n; i++) {
  156.                 for (int j = 0; j < n; j++) {
  157.                     int l = fin.nextInt();
  158.                     if (l == 1) {
  159.                         graph[i].set(j);
  160.     //                    rev[j].set(i);
  161.                     }
  162.                 }
  163.             }
  164.   //          int[] dist = new int[n];
  165.             for (int i = 0; i < n; i++) {
  166.                 fout.println(bfs2(i, graph));
  167. //                bfs(i,dist,n,rev);
  168. //                int currentAns = Integer.MAX_VALUE;
  169. //                for (int v = graph[i].nextSetBit(0); v != -1; v = graph[i].nextSetBit(v + 1)) {
  170. //                    if (dist[v] != -1) {
  171. //                        currentAns = Math.min(currentAns, 1 + dist[v]);
  172. //                    }
  173. //                }
  174. //                if (currentAns == Integer.MAX_VALUE) {
  175. //                    fout.println("NO WAY");
  176. //                } else {
  177. //                    fout.println(currentAns);
  178. //                }
  179.             }
  180.             fout.close();
  181.         } catch (Exception e) {
  182.             e.printStackTrace();
  183.             return;
  184.         }
  185.     }
  186. }
  187.  
Success #stdin #stdout 0.14s 55536KB
comments (?)
stdin
copy 
5
0 1 0 0 1
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
stdout
copy 
2
5
5
5
2
https://ideone.com/RcswvX
problem ADACYCLE, based on SPOJ submission 35449197 (JAVA), 2026-01-12 20:48:38
language:
Java (HotSpot 12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!