Submission #7504705


Source Code Expand

import java.io.*;
import java.util.*;

class Node implements Comparable<Node> {
  int index;
  int cost;
  
  Node(int index, int cost) {
    this.index = index;
    this.cost = cost;
  }
  
  public int compareTo(Node node) {
    return this.cost - node.cost;
  }
}

class Solver {
  final int n, m;
  final int[] ks;
  final int[][] lm;
  List<List<Integer>> graph;
  
  Solver(int n, int m, int[] ks, int[][] lm) {
    this.n = n;
    this.m = m;
    this.ks = ks;
    this.lm = lm;
  }
  
  private Node dijkstra(int speakerIndex) {
    boolean[] visited = new boolean[n + m + 1];
    PriorityQueue<Node> queue = new PriorityQueue<>();
    queue.add(new Node(speakerIndex, 0));
    
    Node maxSpeakerCostNode = new Node(0, 0);;
    while (!queue.isEmpty()) {
      Node node = queue.poll();
      int index = node.index;
      int cost = node.cost;
      if (visited[index]) {
        continue;
      }
      visited[index] = true;
      if (index < n && maxSpeakerCostNode.compareTo(node) > 0) {
        maxSpeakerCostNode = node;
      }
      
      for (int nextIndex : graph.get(index)) {
        if (visited[nextIndex]) {
          continue;
        }
        queue.add(new Node(nextIndex, cost + 1));
      }
    }
    
    for (int i = 0; i < n; i++) {
      if (!visited[i]) {
        return new Node(0, Integer.MAX_VALUE);
      }
    }
    return maxSpeakerCostNode;
  }
  
  public boolean solve() {
    graph = new ArrayList<>();
    for (int i = 0; i <= n + m; i++) {
      graph.add(new ArrayList<>());
    }
    
    for (int speaker = 0; speaker < n; speaker++) {
      for (int j : lm[speaker]) {
        int language = j + n;
        graph.get(speaker).add(language);
        graph.get(language).add(speaker);
      }
    }
    
    Node node1 = dijkstra(0);
    if (node1.cost > 4) {
      return false;
    }
    Node node2 = dijkstra(node1.index);
    return node2.cost <= 4;
  }
}

public class Main {
  private static void execute(ContestReader reader, PrintWriter out) {
    int n = reader.nextInt();
    int m = reader.nextInt();
    int[] ks = new int[n];
    int[][] lm = new int[n][];
    for (int i = 0; i < n; i++) {
      ks[i] = reader.nextInt();
      lm[i] = reader.nextIntArray(ks[i]);
    }
    out.println(new Solver(n, m, ks, lm).solve() ? "YES" : "NO");
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestReader {
  private BufferedReader reader;
  private StringTokenizer tokenizer;
  
  ContestReader(InputStream in) {
    reader = new BufferedReader(new InputStreamReader(in));
  }
  
  public String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }
  
  public int nextInt() {
    return Integer.parseInt(next());
  }
  
  public long nextLong() {
    return Long.parseLong(next());
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] nextArray(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public int[] nextIntArray(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLongArray(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDoubleArray(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public int[][] nextIntMatrix(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public long[][] nextLongMatrix(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDoubleMatrix(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
}

class ModCalculator {
  private final long mod;
  
  ModCalculator(long mod) {
    this.mod = mod;
  }
  
  public long add(long a, long b) {
    return (a + b) % mod;
  }
  
  public long mul(long a, long b) {
    return (a * b) % mod;
  }
  
  public long pow(long a, long b) {
    if (b == 0) {
      return 1;
    }
    long v = pow(mul(a, a), b / 2);
    if (b % 2 == 1) {
      return mul(v, a);
    } else {
      return v;
    }
  }
  
  public long inverse(long a) {
    return pow(a, mod - 2);
  }
  
  public long div(long a, long b) {
    return mul(a, inverse(b));
  }
}
 
class ModCombinationCache {
  private final ModCalculator modCalculator;
  private final List<Long> factorialCache;
  private final List<Long> factorialInverseCache;
  
  public ModCombinationCache(ModCalculator modCalculator) {
    this.modCalculator = modCalculator;
    factorialCache = new ArrayList<>();
    factorialCache.add(1L);
    factorialInverseCache = new ArrayList<>();
    factorialInverseCache.add(1L);
  }
  
  private void resize(int n) {
    for (int i = factorialCache.size() - 1; i < n; i++) {
      long v = modCalculator.mul(factorialCache.get(i), i + 1);
      factorialCache.add(v);
      factorialInverseCache.add(modCalculator.inverse(v));
    }
  }
  
  public long getP(int n) {
    resize(n);
    return factorialCache.get(n);
  }
  
  public long getC(int n, int k) {
    resize(n);
    return modCalculator.mul(factorialCache.get(n), modCalculator.mul(factorialInverseCache.get(k), factorialInverseCache.get(n-k)));
  }
}

class Algorithm {
  private static void swap(Object[] list, int a, int b) {
    Object tmp = list[a];
    list[a] = list[b];
    list[b] = tmp;
  }
  
  public static <T extends Comparable<? super T>> boolean nextPermutation(T[] ts) {
    int rightMostAscendingOrderIndex = ts.length - 2;
    while (rightMostAscendingOrderIndex >= 0 &&
        ts[rightMostAscendingOrderIndex].compareTo(ts[rightMostAscendingOrderIndex + 1]) >= 0) {
      rightMostAscendingOrderIndex--;
    }
    if (rightMostAscendingOrderIndex < 0) {
      return false;
    }
    
    int rightMostGreatorIndex = ts.length - 1;
    while (ts[rightMostAscendingOrderIndex].compareTo(ts[rightMostGreatorIndex]) >= 0) {
      rightMostGreatorIndex--;
    }
    
    swap(ts, rightMostAscendingOrderIndex, rightMostGreatorIndex);
    for (int i = 0; i < (ts.length - rightMostAscendingOrderIndex - 1) / 2; i++) {
      swap(ts, rightMostAscendingOrderIndex + 1 + i, ts.length - 1 - i);
    }
    return true;
  }
  
  public static void shuffle(int[] array) {
    Random random = new Random();
    int n = array.length;
    for (int i = 0; i < n; i++) {
      int randomIndex = i + random.nextInt(n - i);
      
      int temp = array[i];
      array[i] = array[randomIndex];
      array[randomIndex] = temp;
    }
  }
  
  public static void shuffle(long[] array) {
    Random random = new Random();
    int n = array.length;
    for (int i = 0; i < n; i++) {
      int randomIndex = i + random.nextInt(n - i);
      
      long temp = array[i];
      array[i] = array[randomIndex];
      array[randomIndex] = temp;
    }
  }
  
  public static void sort(int[] array) {
    shuffle(array);
    Arrays.sort(array);
  }
  
  public static void sort(long[] array) {
    shuffle(array);
    Arrays.sort(array);
  }
}

class UnionFind {
  int[] parents;
  int[] ranks;

  UnionFind(int n) {
    parents = new int[n];
    ranks = new int[n];

    for (int i = 0; i < n; i++) {
      parents[i] = i;
    }
  }

  public int getRoot(int index) {
    if (parents[index] == index) {
      return index;
    } else {
      parents[index] = getRoot(parents[index]);
      return parents[index];
    }
  }

  public boolean sameGroup(int a, int b) {
    return getRoot(a) == getRoot(b);
  }

  public void merge(int a, int b) {
    int rootA = getRoot(a);
    int rootB = getRoot(b);
    if (rootA == rootB) {
      return;
    }
    if (ranks[rootA] < ranks[rootB]) {
      parents[rootA] = rootB;
    } else if (ranks[rootB] < ranks[rootA]) {
      parents[rootB] = rootA;
    } else {
      parents[rootA] = rootB;
      ranks[rootB]++;
    }
  }
}

Submission Info

Submission Time
Task C - Interpretation
User toshihoge
Language Java8 (OpenJDK 1.8.0)
Score 400
Code Size 9101 Byte
Status AC
Exec Time 406 ms
Memory 62332 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 200 / 200
Status
AC × 2
AC × 12
AC × 27
Set Name Test Cases
sample sample-01.txt, sample-02.txt
dataset1 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt
dataset2 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt AC 73 ms 17364 KB
01-02.txt AC 89 ms 22100 KB
01-03.txt AC 90 ms 18772 KB
01-04.txt AC 104 ms 18900 KB
01-05.txt AC 101 ms 18772 KB
01-06.txt AC 93 ms 21588 KB
01-07.txt AC 92 ms 17492 KB
01-08.txt AC 91 ms 21588 KB
01-09.txt AC 94 ms 21460 KB
01-10.txt AC 95 ms 21332 KB
02-01.txt AC 358 ms 54676 KB
02-02.txt AC 328 ms 51404 KB
02-03.txt AC 275 ms 45716 KB
02-04.txt AC 368 ms 62332 KB
02-05.txt AC 375 ms 53952 KB
02-06.txt AC 342 ms 57700 KB
02-07.txt AC 394 ms 54448 KB
02-08.txt AC 270 ms 51608 KB
02-09.txt AC 406 ms 58056 KB
02-10.txt AC 389 ms 56360 KB
02-11.txt AC 316 ms 55348 KB
02-12.txt AC 370 ms 55808 KB
02-13.txt AC 327 ms 54888 KB
sample-01.txt AC 72 ms 23380 KB
sample-02.txt AC 74 ms 19028 KB