Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class magicmatrix {
- private static InputReader in;
- private static PrintWriter out;
- public static ArrayList<Integer>[] graph;
- public static void main(String[] args) throws IOException {
- in = new InputReader(System.in);
- out = new PrintWriter(System.out, true);
- int n = in.nextInt();
- int[][] d = new int[n][n];
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- d[i][j] = in.nextInt();
- }
- }
- boolean ok = true;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- if (d[i][j] != d[j][i]) ok = false;
- if (d[i][i] != 0) ok = false;
- }
- }
- if (!ok) {
- out.println("NOT MAGIC");
- out.close();
- System.exit(0);
- }
- graph = new ArrayList[n];
- for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
- int[] prev = new int[n];
- int[] min = new int[n];
- Arrays.fill(min, 1 << 30);
- min[0] = 0;
- int[] vis = new int[n];
- int vidx = 1;
- for (int i = 0; i < n; i++) {
- int idx = 0, mn = 1 << 30;
- for (int j = 0; j < n; j++) {
- if (vis[j] < vidx && min[j] < mn) {
- mn = min[j];
- idx = j;
- }
- }
- vis[idx] = vidx;
- if (i > 0) {
- graph[idx].add(prev[idx]);
- graph[prev[idx]].add(idx);
- }
- for (int j = 0; j < n; j++) {
- if (vis[j] < vidx && d[idx][j] < min[j]) {
- min[j] = d[idx][j];
- prev[j] = idx;
- }
- }
- }
- ++vidx;
- int[] queue = new int[n];
- int[] ret = new int[n];
- outer : for (int i = 0; i < n; i++) {
- int front = 0, back = 0;
- queue[back++] = i;
- vis[i] = vidx;
- ret[i] = 0;
- while(front<back) {
- int node = queue[front++];
- for (int next : graph[node]) {
- if(vis[next] >= vidx) continue;
- ret[next] = Math.max(ret[node], d[next][node]);
- if (ret[next] != d[i][next]) {
- ok = false;
- break outer;
- }
- vis[next] = vidx;
- queue[back++] = next;
- }
- }
- ++vidx;
- }
- out.println(ok ? "MAGIC" : "NOT MAGIC");
- out.close();
- System.exit(0);
- }
- static class InputReader {
- public BufferedReader reader;
- public StringTokenizer tokenizer;
- public InputReader(InputStream stream) {
- reader = new BufferedReader(new InputStreamReader(stream), 32768);
- tokenizer = null;
- }
- public String next() {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- try {
- tokenizer = new StringTokenizer(reader.readLine());
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- return tokenizer.nextToken();
- }
- public int nextInt() {
- return Integer.parseInt(next());
- }
- }
- }
Add Comment
Please, Sign In to add comment