SHARE
TWEET

Untitled

edvard_davtyan Mar 1st, 2016 129 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class magicmatrix {
  5.   private static InputReader in;
  6.   private static PrintWriter out;
  7.  
  8.   public static ArrayList<Integer>[] graph;
  9.  
  10.   public static void main(String[] args) throws IOException {
  11.     in = new InputReader(System.in);
  12.     out = new PrintWriter(System.out, true);
  13.  
  14.     int n = in.nextInt();
  15.     int[][] d = new int[n][n];
  16.     for (int i = 0; i < n; i++) {
  17.       for (int j = 0; j < n; j++) {
  18.         d[i][j] = in.nextInt();
  19.       }
  20.     }
  21.     boolean ok = true;
  22.     for (int i = 0; i < n; i++) {
  23.       for (int j = 0; j < n; j++) {
  24.         if (d[i][j] != d[j][i]) ok = false;
  25.         if (d[i][i] != 0) ok = false;
  26.       }
  27.     }
  28.     if (!ok) {
  29.       out.println("NOT MAGIC");
  30.       out.close();
  31.       System.exit(0);
  32.     }
  33.  
  34.     graph = new ArrayList[n];
  35.     for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
  36.     int[] prev = new int[n];
  37.     int[] min = new int[n];
  38.     Arrays.fill(min, 1 << 30);
  39.     min[0] = 0;
  40.     int[] vis = new int[n];
  41.     int vidx = 1;
  42.     for (int i = 0; i < n; i++) {
  43.       int idx = 0, mn = 1 << 30;
  44.       for (int j = 0; j < n; j++) {
  45.         if (vis[j] < vidx && min[j] < mn) {
  46.           mn = min[j];
  47.           idx = j;
  48.         }
  49.       }
  50.       vis[idx] = vidx;
  51.       if (i > 0) {
  52.         graph[idx].add(prev[idx]);
  53.         graph[prev[idx]].add(idx);
  54.       }
  55.       for (int j = 0; j < n; j++) {
  56.         if (vis[j] < vidx && d[idx][j] < min[j]) {
  57.           min[j] = d[idx][j];
  58.           prev[j] = idx;
  59.         }
  60.       }
  61.     }
  62.     ++vidx;
  63.    
  64.     int[] queue = new int[n];
  65.     int[] ret = new int[n];
  66.     outer : for (int i = 0; i < n; i++) {
  67.       int front = 0, back = 0;
  68.       queue[back++] = i;
  69.       vis[i] = vidx;
  70.       ret[i] = 0;
  71.       while(front<back) {
  72.         int node = queue[front++];
  73.         for (int next : graph[node]) {
  74.           if(vis[next] >= vidx) continue;
  75.           ret[next] = Math.max(ret[node], d[next][node]);
  76.           if (ret[next] != d[i][next]) {
  77.             ok = false;
  78.             break outer;
  79.           }
  80.           vis[next] = vidx;
  81.           queue[back++] = next;
  82.         }
  83.       }
  84.       ++vidx;
  85.     }
  86.    
  87.     out.println(ok ? "MAGIC" : "NOT MAGIC");
  88.     out.close();
  89.     System.exit(0);
  90.   }
  91.  
  92.   static class InputReader {
  93.     public BufferedReader reader;
  94.     public StringTokenizer tokenizer;
  95.  
  96.     public InputReader(InputStream stream) {
  97.       reader = new BufferedReader(new InputStreamReader(stream), 32768);
  98.       tokenizer = null;
  99.     }
  100.  
  101.     public String next() {
  102.       while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  103.         try {
  104.           tokenizer = new StringTokenizer(reader.readLine());
  105.         } catch (IOException e) {
  106.           throw new RuntimeException(e);
  107.         }
  108.       }
  109.       return tokenizer.nextToken();
  110.     }
  111.  
  112.     public int nextInt() {
  113.       return Integer.parseInt(next());
  114.     }
  115.   }
  116.  
  117.  
  118. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top